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$
  • 4
    $\begingroup$ The limit is 1 and by definition of little-o it must be 0 $\endgroup$ – Eugene Apr 11 '17 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$ – David Richerby Apr 11 '17 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$ – David Richerby Apr 11 '17 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$ – David Richerby Apr 11 '17 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$ – David Richerby Apr 11 '17 at 19:20
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, privacy policy and cookie policy

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