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}