1
$\begingroup$

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?

3 Answers 3

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

1

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