# Why is $\log(n!)$ $O(n\log n)$?

I thought that $\log(n!)$ would be $\Omega(n \log n )$, but I read somewhere that $\log(n!) = O(n\log n)$.

Why?

-
$$\log n! =\sum_{k=1}^n \log k \leq \sum_{k=1}^n \log n$$ – Pedro Tamaroff May 4 '12 at 16:02
The two statements you give are consistent. In fact both are true. – Qiaochu Yuan May 4 '12 at 16:03
$\log(n!)$ is actually $\Theta(n \log n )$. See math.stackexchange.com/questions/46892/… – lhf May 4 '12 at 16:12
@lhf Indeed, $\dfrac 1 2 n \log n$ and $n \log n$ suffice. – Pedro Tamaroff May 4 '12 at 16:14
The obvious inequalities $(n/2)^{n/2} \leq n! \leq n^n$ suffice to prove $\Theta(n \log n)$. – sdcvvc May 4 '12 at 16:18

One idea

$$\log n! =\sum_{k=1}^n \log k \leq \sum_{k=1}^n \log n=n\log n$$

The other approach would be

$$n !\sim \frac{n^n}{e^n}\sqrt{2 \pi n}$$

From where

$$\log n !\sim n\log n -n+\frac{1}{2} \log \pi n$$

$$\frac{\log n !}{n \log n}\sim 1-\frac 1 {\log n}+\frac{1}{2} \frac {\log \pi n} {n \log n}$$

-
Thanks! Using Stirling's Approximation like that does the trick. – David Faux May 23 '12 at 21:25

By Stolz Cezaro

$$\lim_{n \to \infty} \frac{\ln (n!)}{n \ln n}=lim_{n \to \infty} \frac{\ln ((n+1)!)- \ln(n!)}{(n+1) \ln (n+1)-n \ln n}=lim_{n \to \infty} \frac{\ln ((n+1))}{\ln (n+1)+n [\ln(n+1)- \ln n]}$$

$$=lim_{n \to \infty} \frac{\ln ((n+1))}{\ln (n+1)+ [\ln(1+ \frac{1}{n})^n]}=1$$

Thus $$\ln (n!) \sim n \ln n$$

This implies both big O and Omega...

-