How to check if $n!$ is $ O(2^n)$

Question

How can I check if $n! \in O(2^n)$?

The definition of $f$ being $O(g)$ is $f(n) \le c g (n)$, where $c>0$. So it would mean $n! \le c 2^n$.

What is the clearest way to solve this? (As I am solving the past papers for my next examen.)

Thank you!

Answer 1

As you said you need to check if there is a constant $C>0$ such that $n! \le C 2^n$ for all $n$ (or at least all sufficiently large $n$, but it does not matter much).

Note it is crucial that $C$ does not depend on $n$.

In this case it turns out there is no such $C$. There are various ways to see this. One of them could go like this.

Assume there is such a $C$. Then

$n! \le C 2^n$ for all sufficiently large $n$.

Then $\prod_{i=1}^n \frac{i}{2} \le C$ for all sufficiently large $n$.

Yet for $i \neq 1$ we fave $\frac{i}{2}\ge 1$, so that $\prod_{i=1}^n \frac{i}{2} \ge \frac{1}{2} \frac{n}{2}$ (for $n \ge 2$).

Thus we get $\frac{n}{4} \le C$ for all sufficiently large $n$, which is absurd.

Answer 2

It is not. Intuitively, $n!$ has $n$ factors and most of them are larger than $2$. The ratio gets larger and larger, so you should expect $\frac {n!}{2^n}$ to grow without bound.

A very simple proof by induction is that $\frac {4!}{2^4} \gt 1$. Assume $\frac {k!}{2^k} \gt 1,$ then $\frac {(k+1)!}{2^{k+1}} \gt \frac {k+1}2$ which grows without bound.

Answer 3

A simple proof without induction: suppose there exists a constant $C>0$ such that $n!\le 2^n$. Note $n!\ge2^{n-1}$ for all $n\ge 1$, hence for all $n>1$, $$n=\frac{n!}{(n-1)!}\le \frac{C2^n}{2^{n-2}}=4C$$ from which we conclude that $\mathbf N$ is bounded from above…

Answer 4

Let $h(n)=\frac{n!}{2^n}=\frac{f(n)}{g(n)}$. Note that $h(n)=h(n-1)\frac{n}{2}$. In order for $h(n)\le C$ for all $n$ for some $C>0$ fixed, we need $h(n)$ to stay constant or decrease after some $N$. But for $n\ge 2$, $h(n)$ is increasing since $\frac{n}{2}\ge 1$.