I have to prove the following theorem:
I am not asking for the whole problem, but am stuck on the first part (Proving that output of c implies g(n) is in the order of f(n)).
I know the following:
The order of f(n) is the set of complexity functions g(n) for which there exists some positive real constants c and d and some nonnegative integer N such that, for all n >= N: $c * f(n) <= g(n) <= d * f(n)$
At this point, I feel that I may be able to use induction with the formula above to show that the limit of g(n)/f(n) is nonnegative, but I can't quite wrap my head around that. Or perhaps there is another way to show that the limit converges?
$$\lim_{n \to +\infty} \frac{g(n)}{f(n)}=c$$ means that $\forall \epsilon>0, \exists n_0 \in \mathbb{N}$ such that $\forall n \geq n_0:$ $$\left |\frac{g(n)}{f(n)}-c \right | < \epsilon \Rightarrow - \epsilon< \frac{g(n)}{f(n)}-c< \epsilon \Rightarrow c- \epsilon< \frac{g(n)}{f(n)}<c+\epsilon \\ \Rightarrow (c-\epsilon)f(n)< g(n)<(c+\epsilon) f(n)$$
We pick $\epsilon=\frac{c}{2}$ and we have that $\forall n \geq n_0:$
$$\frac{c}{2} \cdot f(n)< g(n)< \frac{3c}{2} \cdot f(n)$$
Now pick $c_1=\frac{c}{2}, c_2=\frac{3c}{2}$ and you will see that this is the definition of $g(n)=\Theta(f(n))$.