Big-O: Prove $2^n$ is $O(n!)$

Question

I am a little stuck trying to prove that $2^n$ is $O(n!)$. Obviously, I can tell in a few ways that this is the case. For one, based on Big-$O$ hierarchy, the exponential is beneath the factorial in terms of complexity. I also substituted $C = 2$ and tried several values of $n$, all following the Big-$O$ definition of $f(n) \le cg(n)$.

However, my professor says neither of these is a sufficient justification and I should be able to use the definition alone.

How can I do this? I know in the past it has been advantageous for me to compare the functions by converting one into a form that resembles the other, but I just can't figure out how to relate the factorial and $2^n$ functions.

Can anyone point me in the right direction?

Answer 1

Can you show $$\lim_{n\to\infty}\frac{2^n}{n!}=0\text{ ?}$$

Hint $$\frac{2^n}{n!}=\frac{2}{1}\frac{2}{2}\frac{2}{3}\cdots\frac{2}{n-1}\frac{2}{n}$$

so as soon as $n\geq 4$, this is

$$\frac{2^n}{n!}\leq \frac{2}{1}\frac{2}{2}\cdot1\cdots 1\cdot \frac{2}{n}=\frac{4}{n}$$

Then choose, say, $\epsilon =1$..

ADD Let $a_n=2^n,b_n=n!$. Then showing $$a_n\leq C\cdot b_n$$ eventually is equivalent to showing $$\log a_n\leq \log C+\log b_n$$ eventually, that is $$n\log 2\leq \log C+\log n!$$

In the left hand side, we sum $\log 2$ $n$ times, while on the right hand side we sum $\log 2,\log 3,\dots$ and so on. This is essentially the idea I gave before: in one, the product is fixed: one always multiplies by $2$; while in the other the factors grow without bound.

Answer 2

HINT:

$$\frac{\frac{2^{n+1}}{(n+1)!}}{\frac{2^n}{n!}}=\frac{2^{n+1}n!}{2^n(n+1)!}=\frac2{n+1}$$

Answer 3

We have $$ \sum_{n=0}^{\infty} \frac{2^n}{n!} = e^2 < \infty, $$ hence $2^n/n! \to 0$. This means $2^n = O(n!)$.

Hope that helps,

Answer 4

Let $u_n=\frac{2^n}{n!}$ then by ratio test we have $$\frac{u_{n+1}}{u_n}=\frac{2}{n+1}\to_\infty 0$$ hence the sequence $(u_n)$ is convergent to $0$ and then we find that $2^n=O(n!)$ and more precisely $2^n=o(n!)$