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.