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?
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...
One idea to prove the claim :
$$\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}$$
Add: You are correct. It is important to note that $\mathrm{O}$ and $\Omega$ are not mutually exclusive. Because $n\log n$ is both $\Omega$ and $\mathrm{O}$, we say that : $$\log n! = \Theta(n \log n)$$