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?

  • $\begingroup$ I was editing at same time, I dont saw your edit @MithleshUpadhyay. You can edit whatever you want, no problem. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Aditya pratap singh Jun 22 '16 at 7:41
  • $\begingroup$ @Adityapratapsingh You aren't wrong, your argument is simply incomplete. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.