# How to prove this approximation of logarithm of factorial

In other words, how to prove this equation

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

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

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

-
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

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

-

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

-
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

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

-
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