Showing $\lg(n!) = \Omega(n\lg n)$

Question

I saw this equation in "Introduction to Algorithm" 3th edition in page 58 :

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

If $\lg(n!) = \Omega(n\lg(n))$ and $\lg(n!) = O(n\lg(n))$ then we can prove that.

I can easily show $\lg(n!) = O(n\lg(n))$, but I have no idea about $\Omega$.

Answer 1

Since $n=\prod_{j=1}^{n-1}\left(1+\frac{1}{j}\right)$, we have:

$$ n! = \frac{n^{n-1}}{\prod_{j=1}^{n-1}\left(1+\frac{1}{j}\right)^j}\tag{1}$$ but for any $n\geq 1$ we also have: $$ \left(1+\frac{1}{j}\right)^{j+\frac{1}{2}}\geq e,\qquad \left(1+\frac{1}{j}\right)^{j}\leq e,\tag{2} $$ hence: $$ \frac{n^{n-1}}{e^{n-1}}\leq n! \leq \frac{n^{n-\frac{1}{2}}}{e^{n-1}}\tag{3}$$ and by taking logs it follows that $\log(n!)$ is both $O(n\log n)$ and $\Omega(n\log n)$ as $n\to +\infty$.

Answer 2

By the inequality of geometric and harmonic means, we have:

$$\sqrt[n]{n!} > \frac{n}{\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}} = \frac{n}{H_n} = \Theta\left(\frac{n}{\ln(n)}\right)$$

Therefore

$$\ln(n!) \in \Omega\left(n\ln\left(\frac{n}{\ln(n)}\right)\right)$$

$$\ln(n!) \in \Omega\left(n\ln(n)-n\ln(\ln(n))\right)$$

$$\ln(n!) \in \Omega\left(n\ln(n)\right)$$

$$\lg(n!) \in \Omega\left(n\lg(n)\right)$$