Question about proof that $n! = \omega(2^n)$

Question

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$?

Answer 1

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.

Answer 2

I think the previous answer that is currently ticked is wrong please read this link

c's value must be a constant and independent of n, but may depend on n₀ which in the link is referred to as k. So, it can be 1.

(If this is wrong please delete this)

To prove f(n)=ω(g(n)) we must prove that

$\lim_{x \to \infty}\frac{ f(n)}{g(n)}$=$\infty$

which is proved by this link that was given in the question also.

​