My professor defines the Limit Ratio Theorem as follows:
Assume that $\displaystyle\lim_{n \mapsto \infty} \frac{f(n)}{g(n)}=c$, where $c$ is a constant or $\infty$.
- If $0 \leq c < \infty$, then $f(n) = O(g(n))$.
- If $0 < c \leq \infty$, then $f(n) = \Omega(g(n))$.
- If $0 < c < \infty$, then $f(n) = \Theta(g(n))$.
However, I have been unable to find any information on this theorem. Does it go by some other name?
My task is to prove part 3 for any given positive functions $f(n)$ and $g(n)$.
I understand intuitively that if $f(n)$ is $\Theta(g(n))$, then $f(n)$ is $O(g(n))$ and $f(n)$ is $\Omega(g(n))$, which means $f(n)$ and $g(n)$ are of the same order, which means $\lim\limits_{n\to\infty} \frac{f(n)}{g(n)}$ will not equal $\infty$ or $0$ because the variables will cancel, leaving a constant $c$ that is between $0$ and $\infty$.
I realize this is not a rigorous proof. Can anyone suggest a trick to get me started on a more thorough proof? We just covered induction, but I don't see how that can be used.
For your "proof" note that $\lim \frac{f(n)}{g(n)}$ need not exist in general. Also, you seem to try to prove a wrong direction.
Simply note that
$$ \begin{align}&0<c<\infty\\\iff &0\le c<\infty \land 0< c\le\infty \\\implies &f(n)=O(g(n)) \land f(n)=\Omega(g(n)) \\\iff &f(n)=\Theta(g(n)).\end{align}$$