$3[$CLRS $3\mathrm{.}2-3]$

Prove that $lg(n!)in(nlgn).$ Also prove that $n!in(2^n)$ and $n!$inO$(n^n).$

Hint: Use Stirling's approximation: $n\sqrt[\phantom{2}]{2n}(\frac{n}{e}{)}^n(1+(\frac{1}{n}))$