Formally verifying that $n \log n = o(n^2)$

Question

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.

Answer 1

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

Answer 2

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.