How to check if $n!$ is $ O(2^n)$ 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!
 A: 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.
A: 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.
A: 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…
A: 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$.
