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

Prove equation (3.19) states: \(\lg(n!) = \Theta(n \lg n)\)

For this proof, we will use Stirling’s approximation as stated in the chapter text (equation 3.18).

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:

\[\begin {aligned} \lg(n!) & \approx \lg\left(\sqrt{2πn} \left(\frac n e \right)^n \right) \\ & = \lg\left(\sqrt{2πn}\right) + \lg\left(\frac n e \right)^n \\ & = \lg\sqrt {2π} + \lg \sqrt n + n \lg\left(\frac n e \right) \\ & = \lg\sqrt {2π} + \frac 1 2 \lg n + n \lg n - n \lg e \\ & = \Theta(1) + \Theta(\lg n) + \Theta(n \lg n) - \Theta(n) \\ & = \Theta(n \lg n) \end {aligned}\]

Small Omega

\(n! = \omega(2^n)\) can be shown using the limit definition as follows:

\[\begin{aligned} \lim_{n \to \infty} \frac {n!} {2^n} & = \lim_{n \to \infty} \frac {\sqrt{2πn} \left(\frac n e \right)^n\left(1 + \Theta(\frac 1 n)\right)} {2^n} \\ & = \sqrt{2π} \times \lim_{n \to \infty} \sqrt n \left(\frac {n} {2e}\right)^n \times \lim_{n \to \infty} \left(1 + \Theta\left(\frac 1 n\right)\right) \\ & = \sqrt{2π} \times \infty \times 1 \\ & = \infty \end {aligned}\]

Small Oh

Similarly, \(n! = o(n^n)\) can be shown as follows:

\[\begin{aligned} \lim_{n \to \infty} \frac {n!} {n^n} & = \lim_{n \to \infty} \frac {\sqrt{2πn} \left(\frac n e \right)^n\left(1 + \Theta(\frac 1 n)\right)} {n^n} \\ & = \sqrt{2π} \times \lim_{n \to \infty} \frac {\sqrt n} {e^n} \times \lim_{n \to \infty} \left(1 + \Theta\left(\frac 1 n\right)\right) \\ & = \sqrt{2π} \times 0 \times 1 \\ & = 0 \end {aligned}\]