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

Question

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?

Answer 1

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.

Answer 2

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.