I am trying to verify that $n \log n = o(n^2)$ using the formal definition of small-o.

The definition of small-o is as follows

Let $f$ and $g$ be functions $f,g: \mathbb{N} \rightarrow \mathbb R^+$. We say that $f(n)=o(g(n))$ if $\lim_{n\to\infty} \frac{f(n)}{g(n)}=0$.

This can be stated as saying $f(n)=o(g(n))$ means that for any real number $c>0$ there exist a number $n_0$, where $f(n) < c \, g(n)$ for all $n \geq n_0$.

I would like an intuitive clarification of the difference between big-O and small-o notation, and given an intuitive explanation of why $n \log n = o(n^2)$, as well as a formal proof. I hope this will clear up any of my misunderstandings.

  • 1
    $\begingroup$ Do you how to prove $\lim_{x \to \infty} \frac{x \log x}{x^2} = 0$ from the definition of a limit? $\endgroup$ – Srivatsan Sep 16 '11 at 1:40
  • $\begingroup$ Not too sure how to do that. This will be the first time that I see such a limit proof. $\endgroup$ – binaryop Sep 16 '11 at 1:42
  • $\begingroup$ Do you know about Hopital's rule? $\endgroup$ – Hassane Kone Sep 16 '11 at 1:45

$\lim_{n \to \infty} \frac{n \log n}{n^2}=\lim_{n \to \infty} \frac{\log n}{n}=\lim_{n \to \infty} \frac{1}{n}=0$

The last step is due to the fact that both numerator and denominator tend to infinity and $n \to \infty$, so you can apply L'Hospital's rule and differentiate both. The limit is $0$, therefore $f(n)=o(g(n))$.

More formally, for an arbitrarily large $n_0, \ n >n_0 \ \exists \ \epsilon>0 $ s.t. $\frac{f(n)}{g(n)} < \epsilon$.

  • $\begingroup$ Thanks this clarifies things quite a bit. $\endgroup$ – binaryop Sep 16 '11 at 2:04

Here $f(n) = n \log n$ and $g(n) = n^2$. (All my logarithms are to base $2$, not $e$.) We are interested in the ratio $$ \frac{f(n)}{g(n)} = \frac{n \log n}{n^2} = \frac{\log n}{n}, $$ as $n$ gets large. Notice that the numerator grows logarithmically, while the denominator grows polynomially. So it is intuitively clear that this ratio is small (i.e., $o(1)$) as $n$ grows large. But we should still prove it rigorously.

One method to do this is the following. First, assume that $n$ is a power of $2$. (We will worry about a general $n$ later.) That is, let $n = 2^k$ and $\log n = k$. Therefore, $$ n = 2^k = (1+1)^k \stackrel{(a)}{=} 1 + k + \binom{k}{2} + \ldots + \binom{k}{k} \geq k + \binom{k}{2} = \frac{k(k+1)}{2} \geq \frac{k^2}{2} = \frac{(\log n)^2}{2}. $$ where $(a)$ follows from the binomial theorem. Therefore, $$ \frac{f(n)}{g(n)} = \frac{\log n }{n} \leq \frac{2 \log n}{(\log n)^2} = \frac{2}{\log n}. $$ Thus we have some upper bound on the ratio, so we are in business.

Now, fix any $c > 0$. Then take $n_0 = 2^{2/c}$. Then, if $n \geq n_0$, then $\log n \geq \frac{2}{c}$. Therefore, $$ \frac{f(n)}{g(n)} \leq \frac{2}{\log n} \leq \frac{2}{(2/c)} = c. $$

Therefore, for every $c > 0$, there exists some $n_0$ (actually, $n_0 = 2^{2/c}$ will work), such that if $n \geq n_0$, the ratio $\frac{f(n)}{g(n)}$ is at most $c$. Hence we are done.

  • $\begingroup$ Thanks for the insightful proof. $\endgroup$ – binaryop Sep 16 '11 at 12:01

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.