I am trying to prove the following statement.
if $\displaystyle \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}= \infty$, then $f(n) = \Omega(g(n))$ but $f(n) \neq O(g(n))$
What I've done so far
Using the definition of limit: $\forall M>0 \quad \exists n_0 : \forall n \ge n_0 \quad \displaystyle\frac{f(n)}{g(n)} > M$
So I multiplied both halves by $g(n)$ obtaining $f(n) > M\cdot g(n)$
I therefore chose a value $c_1$ that respect the condition $0 \le M \le c_1$ in order to define the relation $0 \le c_1g(n)\le f(n)$ that proves that
$f(n) = \Omega(g(n))$
So now my questions are:
- Is the (first part of the) solution mathematically right?
- How can I mathematically prove that $f(n) \neq O(g(n))$?
I'm struggling a bit to prove the second part of the demonstration.
The main idea I had is to do a reductio ad absurdum where I state that the value $c_2$ I get (following the definition of $O(g(n))$) leads me to a contradiction. But I'm not entirely sure it makes sense.
Thank you in advance for your time.