Prove equation (3.19). Which states $\lg(n!) = \Theta(n \lg n)$ Also prove that $n! = \omega(2^n)$ and $n! = o(n^n)$.

For this proof, we will use Stirling’s approximation as stated in the chapter text (equation 3.18). Also for large values of $n$, $\Theta \left(\frac 1 n\right)$ will be very small compared to 1. Hence, for very large values of $n$ we can write $n!$ as follows:

The rest of the two proofs are pretty much intuitive.