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

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.

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.

• I wrote almost the same proof as you wrote above. I wasn't sure if that made sense, but now know for sure! Thank you very much! Jul 22 at 19:48
• @LukeTheWolf this proof is directly following the definition of big-O and the limit definition that you see in calculus classes. It is very formal, but not always as understandable :o Jul 22 at 20:00
• Unfortunately, I know it is very formal, but I was asked to make a formal demonstration. Perhaps can you give me a few more tips on how to make that demonstration easier, but just as effective? Jul 22 at 20:04
• @LukeTheWolf sadly, I do not know of another way, except for using the big-O definition using limits. In that definition, $f$ is said to be $O(g)$ if $\limsup_{n\rightarrow \infty} \frac{f(n)}{g(n)}<\infty$ and as you can see, it is exactly what you asked in the question (and hence not an interesting solution since it just assumes the answer) Jul 22 at 20:27

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))$$.

• Thanks for the reply, but I would like to find the mathematical proof that determines that $f(n) \neq O(g(n))$, could you help me please? Jul 22 at 17:09
• You can take $f(n)=\omega(g(n))$, as a result, $f(n)=\Omega(g(n))$ and $f(n)\neq \mathcal{O}(g(n))$
– Jut
Jul 22 at 17:10
• Ok, thanks for that! Jul 22 at 17:17