Computational complexity proof

Question

I would like to know how to prove the following:
$2^n \in O(n!)$
I know that I have to show that for a constant C, we have $2^n \leq C*n!$
Right?

Answer 1

HINT

Prove that $2^n \leq n!$ for $n \geq 4$. The proof follows immediately from induction.

Answer 2

Not quite right. That would certainly be sufficient, but it’s not necessary: the definition only requires you to find $C>0$ and $m\in\Bbb N$ such that $2^n\le Cn!$ for all $n\ge m$, and there are many pairs $C,m$ that work.

For instance, note that $2^4=16<24=4!$. Now prove by induction that $2^n<n!$ for all $n\ge 4$, and you can use $C=1,m=4$.

Alternatively, prove by induction that $2^n\le2n!$ for all $n\ge 0$, and you can use $C=2,m=0$.

Answer 3

In fact it is easy to show the stronger result, that, $2^n = o(n!)$.