We have the following definitions:
Given two functions $s(n), t(n)$ on $\mathbb{N}$,
$s(n) = O(t(n))$ if there are constants $c, d$ such that for all $n$, $s(n) \leq c \cdot{t(n)} + d$
$s(n) = \Omega(t(n))$ if $t(n) = O(s(n))$
$s(n) = \Theta(t(n))$ if $s(n) = \Omega(t(n))$ and $s(n) = O(t(n))$
My question is: given a function $f: \mathbb{N} \rightarrow \mathbb{N}$, show that it is linear if and only if $f(n) = \Theta(n)$
I was able to show that a function that is linear is $\Theta(n)$. I don't know how to show that a function that is $\Theta(n)$ is necessarily linear because if we apply the definitions:
$f(n) = O(n)$ and $f(n) = \Omega(n)$
Therefore, $f(n) \leq cn + d$ for some constants $c, d$, and $n \leq a \cdot{f(n)} + b$ for some constants $a, b$. I'm not quite sure how to proceed from here. I think the reason I am stuck is because I don't know what a linear function is mathematically. I know that it is a function that is a straight line on the Cartesian axis. But what do I need to show to conclude that a function is linear?
Linearity here means that $f(n) = an + b$ for some constants $a, b \in \mathbb{N}$.
Now the direction you are trying to prove is false. To see this, consider the function $f: \mathbb{N} \to \mathbb{N}$ defined by
$$ f(n) = \begin{cases} n + 1, & \text{if } n \text{ is odd} \\ n + 2, & \text{if } n \text{ is even} \end{cases} $$ Can you show that $f(n)$ is both $\Omega(n)$ and $O(n)$ but is not linear?
It may also make it easier for you to first prove that if there exists constants $a, b \in \mathbb{N}$ such that $a t(n) + b \leq s(n)$, then $s(n) = \Omega \left( t(n) \right)$.