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

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.