How to prove this approximation of logarithm of factorial In other words, how to prove this equation
$$\lg{n!} = \Theta(n\lg{n})$$
 A: 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).
$$
A: 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)$?.
A: $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)$. 
A: 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)$.
