I'm reading CLRS and have came across this sub-question:
Proof that $n! = \omega(2^n)$
I have seen several solutions that are more or less the same as the one stated here. The solution simply says
For all $n \ge 4$, $$\begin{align}n!&= n\cdot(n – 1) \cdot \ldots \cdot 2\cdot 1 \\&> 2 \cdot 2\cdot\ldots \cdot 2\cdot 2\\ &= \omega(2^n)\end{align}$$
Now, I do understand what the above says.
However, what I am confused about is that by the formal definition of $\omega$, we need to prove that
$$\forall C> 0 ~~\exists n_0 > 0 ~~ \forall n \ge n_0~~~~0 \le C\cdot2^n < n!$$
The solution has proved the above case for $C = 1$: For $C = 1$, there exists $n_0 > 0$ (namely $n_0 = 4$) such that for all $n \ge 4$, we have $$0 \le 1\cdot 2^n < n!$$
but this is only for the case $C = 1$, not for all $C > 0$.
Am I right to say that the solution I quoted is incomplete, and that it is necessary to prove the inequality for all values of $C$ instead of just $C = 1$?
Best Answer
You are correct. The proof in question establishes that $n!=\Omega(2^n)$ but not that $n!=\omega(2^n)$. This is a common error and it's good that you caught it.
To prove that $n!=\omega(2^n)$, fix some $C$ and notice that for $n>\max(2C, 4)$, we can bound $(n-1)!$ below by $2^{n-1}$ and $n$ by $2C$ to get $n! < C2^n$.
The $\max(2C, 4)$ requirement is necessary as if $n < 4$ then $2^{n-1}\leq (n-1)!$ does not hold.