0
$\begingroup$

I need to prove that $n^2$ is not $o(n^2+10^{10}n)$. I thought of the limit test: $$ \lim_{n \to \infty} \frac{n^2}{n^2+10^{10}n} = 1 \Rightarrow n^2 = \Theta(n^2+10^{10}n) $$

However I'm not sure if the result of the test rules out the possibility of $o(n^2+10^{10}n)$.

$\endgroup$
14
  • 4
    $\begingroup$ The limit is 1 and by definition of little-o it must be 0 $\endgroup$
    – Eugene
    Apr 11, 2017 at 18:03
  • 4
    $\begingroup$ The definition of $f(n)=o(g(n))$ is that $\lim_{n\to\infty} f(n)/g(n)=0$. For $f(n)=n^2$, $g(n)=n^2+10^{10}n$, you have found that $\lim_{n\to\infty} f(n)/g(n)=1$. So what is your question? $\endgroup$ Apr 11, 2017 at 18:44
  • 1
    $\begingroup$ OK, you're using the other definition of little-o. I'll write up an answer. (By the way, the definition you quote in your comment is big-O, not little-o.) $\endgroup$ Apr 11, 2017 at 18:56
  • 1
    $\begingroup$ @Yos That doesn't make any difference: the distinction is whether $c$ is existentially quantified (big-O) or universally quantified (little-o). $\endgroup$ Apr 11, 2017 at 18:59
  • 2
    $\begingroup$ @Yos The definition of little-o you quote says that for all $c>0$, which is not what you stated. (Compare the definition of big-O on page 47 that says for some $c>0$.) $\endgroup$ Apr 11, 2017 at 19:20

2 Answers 2

6
$\begingroup$

One definition $f(n)=o(g(n))$ is that $\lim_{n\to\infty} f(n)/g(n)=0$. If this is the definition you're using, then showing that the limit is $1$ already shows that $f(n)\neq o(g(n))$.

The other definition is that, for every $c>0$, there is an $n_0$ such that $f(n)\leq cg(n)$ for all $n\geq n_0$. The fact that $\lim_{n\to\infty} f(n)/g(n)=1$ means that, for all $\varepsilon>0$, there is some $n_0$ such that $f(n)/g(n)>1-\varepsilon$ for all $n\geq n_0$ (this is part of the definition of "limit"). So, for all $\varepsilon>0$, we have $f(n)>(1-\varepsilon)g(n)$ for all large enough $n$. This means that, in particular, we do not have $f(n)\leq cg(n)$ for $c=1-\epsilon$, so $f(n)\neq o(g(n))$ by the alternative definition.

$\endgroup$
1
$\begingroup$

Without any limits: $(n^2 + 10^{10}n) / 2 ≤ n^2 ≤ n^2 + 10^{10}n$ whenever $n ≥ 10^{10}$. So for c < 1/2, we don't have $n^2 < c(n^2 + 10^{10}n)$ for all large n. Actually, not for any large n.

And $f(n) = \Theta (g(n))$ does indeed rule out that $f(n) = o (g(n))$, but is not a necessary condition.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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