Prove \(\lg(n!) = \Theta(n \lg n)\). Also prove that \(n! = \omega(2^n)\) and \(n! = o(n^n)\).

Using Stirling’s Approximation:

\[\begin{equation} \begin{split} n! & = \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n \left(1 + \Theta \left( \frac{1}{n} \right) \right) \\ \lg(n!) & = \lg(\sqrt{2 \pi n}) + \lg \left( \left( \frac{n}{e} \right)^n \right) + \lg \left(1 + \Theta \left( \frac{1}{n} \right) \right) \\ & = \Theta(\sqrt{n}) + n \lg \left( \frac{n}{e} \right) + lg\left(\Theta(1) + \Theta \left(\frac{1}{n} \right) \right) \\ & = \Theta(n) + \Theta(n \lg n) + \Theta \left(\frac{1}{n} \right)\\ & = \Theta(n \lg n) \\ \end{split} \end{equation}\]

In order to prove \(n! = \omega(2^n)\) we must show that for any positive constant \(c > 0\), there exists a constant \(n_0 > 0\) such that \(0 \leq c2^n < n! \ \forall \ n \geq n_0\). In order to satisfy this inequality, we must find the point at which \(n!\) overtakes \(2^n\) which occurs when \(n /geq 4\) so then by setting \(n_0 = 4c\) we conclude that \(n! = \omega(2^n)\).

In order to prove \(n! = o(n^n)\) we must show that for any positive constant \(c > 0\), there exists a constant \(n_0 > 0\) such that \(0 \leq n! < cn^n \ \forall \ n \geq n_0\). In order to satisfy this inequality, we must find the point at which \(n^n\) overtakes \(n!\) which occurs when \(n \geq 2\) so then by setting \(n_0 = 2c\) we conclude that \(n! = o(n^n)\).