# Proving $f(n)=100n+5 \neq \Omega(n^2)$

I have to prove that:

$$f(n)=100n+5 \neq \Omega(n^2)$$ What I tried: let's assume that $f(n)=100(n)+5= \Omega(n^2)$. Thus, there must exist some positive constant $c$ and $n_0$ such that, $$0 \leq c(n^2) \leq f(n)$$ $$0 \leq c(n^2) \leq 100n+5$$ $$c(n^2)-100n-5 \leq 0$$ Now the above equation holds only if $c \lt 0$, which contradicts our previous assumption. Therefore we can say that $$f(n)=100n+5 \neq \Omega(n^2)$$

Is this approach wrong? If it is, then what could be a better approach?

• I was editing at same time, I dont saw your edit @MithleshUpadhyay. You can edit whatever you want, no problem. – Masacroso Jun 22 '16 at 7:23

Your approach is lacking. You say

Now,above equation could hold only if $c \lt 0$ ,which contradicts our assumption

Which is the correct idea, but it is not entirely true.

The above equation, for example, holds if $c=1$ and $n=10$.

Now, I assume you know that my counterexample is not good, but it works because you forgot to say that the equation needs to hold *for every $n>n_0$.

Try to write your proof in such a way that I won't be able to provide you counterexamples like the one above.

• got what u said but i'd like to add more that i used concept of quadratic equations here which says,<br/> equation c(n^2)-100n-5<=0 holds true if c<0 and discriminant>=0 so how is a positive c(your example ,c=1 ) satisfying the equation?<br/>Correct me if I am wrong. – Aditya pratap singh Jun 22 '16 at 7:41
• @Adityapratapsingh You aren't wrong, your argument is simply incomplete. – 5xum Jun 22 '16 at 7:42

Let $f(n)$ and $g(n)$ be two function,then

if $\lim \limits_{x \to \infty} \frac{f(n)}{g(n)} =0$ then $f(n)=O(g(n))$ and $g(n)=\Omega(f(n))$

if $\lim \limits_{x \to \infty} \frac{f(n)}{g(n)} =\infty$ then $f(n)=\Omega(g(n))$ and $g(n)=O(f(n))$

if $\lim \limits_{x \to \infty} \frac{f(n)}{g(n)} =k$(constant),then $f(n)=\theta(g(n))$ and $g(n)=\theta(f(n))$

If you try to prove the above statement,you will get your answer.