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.

In other words, how to prove this equation

$$\lg{n!} = \Theta(n\lg{n})$$

share|improve this question
    
Related to math.stackexchange.com/questions/46892/… –  lhf Aug 5 '11 at 0:51
    
Is $\Theta$ the big O? –  Jack Aug 5 '11 at 1:10
    
I'm reading Introduction of Algorithm, $\Theta$ has a different meaning with big O. –  ablmf Aug 5 '11 at 1:23
2  
$\Theta = \mathcal{O} + \Omega$. $\mathcal{O}$ is upper bound, $\Omega$ is lower bound and $\Theta$ is tight bound (both upper and lower). For eg, $n\log n = \mathcal{O}(n^2)$ but not $\Theta(n^2)$, $n \log n = \Omega(n)$ but not $\Theta(n)$ and $n \log n = \Theta(n \log n)$ –  Aryabhata Aug 5 '11 at 1:43
add comment

4 Answers 4

up vote 3 down vote accepted

The easy part is $\log(n!) \le n \log n$, which follows from $n! \le n^n$.

The hard part is discussed in How do you prove that $n^n$ is $O(n!^2)$?.

share|improve this answer
    
I had some trouble to go from $n^n = O(n! ^ 2)$ to $n^n = O(n!)$. –  ablmf Aug 5 '11 at 2:04
    
@ablmf, you take logs and go from $n^n = O(n! ^ 2)$ to $n\log n = O(\log (n!))$. –  lhf Aug 5 '11 at 11:51
    
This is the most simple proof! –  ablmf Aug 5 '11 at 13:57
add comment

Hint: $$ n\log \bigg(\frac{n}{e}\bigg) + 1 \le \log n! \le (n + 1)\log \bigg(\frac{{n + 1}}{e}\bigg) + 1. $$ Taken from Wikipedia, see here.

EDIT: Actually it is stated in that link "Hence $\log n!$ is $\Theta (n\log n)$''.

EDIT 2: The derivation of the above result is given in the Wikipedia link (and is very elementary). Based on it, let's show that $$ \log n! = n \log n - n + O(\log n) \;\; {\rm as}\; n \to \infty, $$ which implies, in particular, that $$ \log n! \sim n\log n \;\; {\rm as}\; n \to \infty $$ (that is, $\log n! / (n\log n) \to 1$ as $n \to \infty$), which implies, in particular, that $\log n!$ is $\Theta (n\log n)$. So, first note that $$ n\log n - n + 1 \le \log n! \le (n + 1)\log (n + 1) - (n + 1) + 1. $$ Hence, $$ n\log n - n + 1 \le \log n! \le n\log (n + 1) + \log (n + 1) - n. $$ Next note that, since $\log(1+x) = x + O(x^2)$ as $x \to 0$, $$ \log(n+1) - \log n = \log \bigg(\frac{{n + 1}}{n}\bigg) = \log \bigg(1 + \frac{1}{n}\bigg) = \frac{1}{n} + O\bigg(\frac{1}{{n^2 }}\bigg), $$ and hence $$ \log(n+1) = \log n + \frac{1}{n} + O\bigg(\frac{1}{{n^2 }}\bigg). $$ Now, $$ n\log n - n + 1 \le \log n! \leq n\bigg[\log n + \frac{1}{n} + O\bigg(\frac{1}{{n^2 }}\bigg)\bigg] + \bigg[\log n + \frac{1}{n} + O\bigg(\frac{1}{{n^2 }}\bigg)\bigg] - n, $$ hence $$ n\log n - n + 1 \le \log n! \leq n\log n - n + \log n + O(1), $$ and finally $$ \log n! = n \log n - n + O(\log n). $$

share|improve this answer
add comment

Looking at the graph of $\log$ one immediately verifies the inequalities $$\int_1^n\log x\ dx <\sum_{k=1}^n\log k<\int_2^{n+1}\log x\ dx\ .$$ Evaluating the integrals one gets $$n\log n -n+1< \log(n!)<(n+1)\log(n+1)-n + c$$ with $c=1-\log 4$, and this easily implies ${\log(n!)\over n\log n}\to 1$ $(n\to\infty)$.

share|improve this answer
    
Nice! I'm not familiar with the $\Theta$ notation. I suspect your statement to be stronger than the one in the title. Is this correct? –  Pierre-Yves Gaillard Aug 5 '11 at 11:17
    
@Pierre-Yves Gaillard: Yes, see here for the definition of various symbols concerning asymptotic behavior: en.wikipedia.org/wiki/Big_O_notation –  Christian Blatter Aug 5 '11 at 11:24
add comment

$e^x = \sum_{n \ge 0} \frac{x^n}{n!}$ implies $e^n \ge \frac{n^n}{n!}$, hence $n! \ge \left( \frac{n}{e} \right)^n$, hence $\log n! \ge n \log n - n$. On the other hand,

$$n! \le \left( \frac{1 + 2 + ... + n}{n} \right)^n = \left( \frac{n+1}{2} \right)^n$$

by AM-GM, hence $\log n! \le n \log \left( \frac{n+1}{2} \right)$.

share|improve this answer
    
Isn'it $n\log n-n$ (not $n\log n-1$)? –  Pierre-Yves Gaillard Aug 5 '11 at 10:47
    
Ah, yes, you're right. –  Qiaochu Yuan Aug 5 '11 at 12:37
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.