Prove $2^n = O(n!)$

Question

I proved by induction that for all $n \leq 4$, $2^n+1 \lt (n+1)!$, therefore $2^n \lt n!$, but I just don't know how to prove the big $O$.

I know the definition that there exists $c$ for which $n! \leq c \cdot 2n$, but I just don't understand how to find $c$.

Answer 1

Hint:

To go from $2^n$ to $2^{n+1}$, you multiply by $2$.

To go from $n!$ to $(n+1)!$, you multiply by $n+1$.

For almost all $n$, $n+1\geq 2$.

Answer 2

You got it backwards, and wrote $2n$ instead of $2^n$. So you want $2^n\le c\cdot n!$. But if you write it out, you have $2\cdot2\dots2/(n\cdot (n-1)\dots2\cdot1)=2/n\cdot2/(n-1)\cdot\dots2/2\cdot2/1\le2$. So we are done.

Actually, we also have that, since $n!$ increases faster than $2^n$, $2^n=o(n!)$. But when one function is little-oh of another function, that implies that it is also big-oh of it.