Prove that $f(n)$ is $= \Omega(g(n))$ but not $= O(g(n))$

Question

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.

Answer 1

Your basic idea is good. Here is how you would approach it:

Let us assume towards contradiction that $\exists c_2,n_0:\forall n>n_0:f(n)\le c_2\cdot g(n)$

In particular, we can re-write this as:

$$\exists c_2,n_0:\forall n>n_0:\frac{f(n)}{g(n)}\le c_2$$

Now, since $\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)}=\infty$, then we know by definition of the limit that $$\forall M>0:\exists n_0:\forall n>n_0:\frac{f(n)}{g(n)}>M$$

In particular, for any $c_2$ and $n_0$, there is some $n>n_0$ with $f(n)>c_2\cdot g(n)$. Hence, we get a contradiction to the assumption.

Answer 2

Suppose $f(n)=n^4,g(n)=n$, so

$$\lim_{n\to\infty}\frac{f(n)}{g(n)}=\frac{n^4}{n^3}=\frac{n^3}{1}=\infty.$$

That means $f(n)=\Omega(g(n))$ and $f(n)\neq\mathcal{O}(g(n)).$ As a result, if $f(n)=\omega(g(n))$, then we can conclude that, $f(n)=\Omega(g(n))$ and $f(n)\neq \mathcal{O}(g(n)).$

Note that in a such case that

$$\lim_{n\to\infty}\frac{f(n)}{g(n)}=\infty$$ easily we can conclude that $f(n)=\omega(g(n))$.