Is $\log(n!) \in\Theta(n \log n)$ Is $\log(n!) \in\Theta(n \log n)$?
I know it is $O(n \log n)$ because $\log(n!) \leq \log(n^n)$ which is the same as $\log(n!) \leq n \log n$.
But how can I show it is also $\Omega(n \log n)$?
 A: This follows from Stirling's formula, but you can also give a very elementary proof.  Note that the $\lfloor n/2\rfloor$ largest factors in $n!$ are all at least $n/2$, so $n!\geq (n/2)^{n/2-1}$.  So $$\log(n!)\geq \left(\frac{n}{2}-1\right)\log\left(\frac{n}{2}\right)=\frac{1}{2}n\log n-\frac{\log{2}}{2}n-\log\left(\frac{n}{2}\right).$$
For $n$ large, $\log 2/2\ll\log n/2$ and $\log(n/2)\ll n\log n$, so we get $\log(n!)\geq Cn\log n$ for any $C<1/2$ for sufficiently large $n$.
In fact, you can replace all the $2$s in the above argument with any $k>1$, and obtain that $\log(n!)$ is eventually greater than $Cn\log n$ for any $C<1/k$.  Letting $k$ approach $1$, you can conclude that in fact $\log(n!)\sim n\log n$.
A: Yes! First notice that
$$ \log(n!) = \sum_{k=1}^n \log(k). $$
As $\log$ is increasing, you'll get
$$\int_{1}^{n+1} \log(t)\mathrm{d}t \geqslant \sum_{k=1}^n \log(k) \geqslant \int_{2}^{n} \log(t)\mathrm{d}t. $$
For $\int_{1}^{x} \log(t)\mathrm{d}t = x\log(x)-x$, you actually have the even better estimate $\log(n!) \sim n\log(n)$.
A: $\log(x)$ is a concave function on $\mathbb{R}^+$, hence the Hermite-Hadamard inequality gives:
$$ \int_{1}^{n+1}\log(x)\,dx \geq \frac{\log(n+1)}{2}+\log(n!) \tag{1}$$
from which $\log(n!)=O(n\log n)$, as well as:
$$   \log(n!)\geq\int_{1/2}^{n+1/2}\log(x)\,dx \tag{2} $$
from which $\log(n!)=\Omega(n\log n)$.
A: We know that $f(n) = \Omega(g(n))$ if and only if $\lim_{n \rightarrow \infty} f(n) / g(n) > 0$ (Wikipedia).
$$\lim_{n \rightarrow \infty} \frac{\log n!}{n \log n} = 1$$
Therefore the answer is yes.
