Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
Thanks this clarifies things quite a bit. –  binaryop Sep 16 '11 at 2:04
add comment

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.

share|improve this answer
    
Thanks for the insightful proof. –  binaryop Sep 16 '11 at 12:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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