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?
Computational complexity proof
1
$\begingroup$
functions
polynomials
computational-complexity
factorial
3 Answers
2
HINT
Prove that $2^n \leq n!$ for $n \geq 4$. The proof follows immediately from induction.
-
0@eouti Yes. Or if you want your base case to be $1$, prove that $2^n \leq 2 n!$ for all $n \geq 0$. – 2012-10-16
1
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
Alternatively, prove by induction that $2^n\le2n!$ for all $n\ge 0$, and you can use $C=2,m=0$.
1
In fact it is easy to show the stronger result, that, $2^n = o(n!)$.