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!$
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Prove that $2^n \leq n!$ for $n \geq 4$. The proof follows immediately from induction.
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$.