[Math] 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?

Best Answer

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.

Related Question