# How to prove that $n^2$ is not $o(n^2+10^{10}n)$?

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)$.

• The limit is 1 and by definition of little-o it must be 0 – Eugene Apr 11 '17 at 18:03
• 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? – David Richerby Apr 11 '17 at 18:44
• 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.) – David Richerby Apr 11 '17 at 18:56
• @Yos That doesn't make any difference: the distinction is whether $c$ is existentially quantified (big-O) or universally quantified (little-o). – David Richerby Apr 11 '17 at 18:59
• @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$.) – David Richerby Apr 11 '17 at 19:20

## 2 Answers

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.

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.