Proving a factorial is not a certain complexity I know this is a stupid question but I will ask it anyway. I need to do complexity analysis for n! to prove that it is not a certain complexity order. How can I go about doing that? 
Problem: Prove that $n!$ is not O($2^n$). 
I'm not sure how I can start this problem. I want to say that I could compare the factorial to the complexity order in an inequality. This confuses me because they are basically two different values. 
 A: If $n!$ were $O(2^n)$, there would be positive constants $n_0$ and $C$ such that $n!\le C\cdot2^n$ for all $n\ge n_0$ or, equivalently, such that $\dfrac{n!}{2^n}\le C$ for all $n\ge n_0$. One way to show that this is not the case is to show that the fraction $\dfrac{n!}{2^n}$ can be made as large as we like by taking $n$ big enough. In other words, it would be sufficient to show that $$\lim_{n\to\infty}\frac{n!}{2^n}=\infty\;.$$
Notice that $$\frac{n!}{2^n}=\frac{n}2\cdot\frac{n-1}2\cdot\frac{n-3}2\cdot\ldots\cdot\frac22\cdot\frac12\;;$$ how does the value of this expression change when you replace $n$ by $n+1$ throughout?
A: As Brian says, what you want to show is that $\displaystyle\frac{n!}{2^n}$ can't be bounded as $n\rightarrow\infty$.  Now, suppose $n\geq 4$: then using Brian's breakdown, we get $\displaystyle\frac{n!}{2^n} = \frac{n}{2}\cdot\frac{n-1}{2}\cdot\ldots\cdot\frac{3}{2}\cdot\frac{2}{2}\cdot\frac{1}{2}$.  But all the terms between $\displaystyle\frac{n-1}{2}$ and $\displaystyle\frac{2}{2}$ are at least $1$, so we know that (at the very least) $\displaystyle\frac{n!}{2^n}\geq\frac{n}{2}\cdot 1\cdot\ldots\cdot 1\cdot\frac{1}{2} = \frac{n}{4}$ for all $n\geq 4$.  Since this expression obviously isn't bounded, then neither is $n!/2^n$, and so we know that it can't be the case that $n!=O(2^n)$.
A: To modify Steven Stadnicki's proof moderately,
since all the numbers from
$n/2$ to $n$ are at least $n/2$ and there are
at least $n/2$ of them,
$n! \ge (n/2)^{n/2} = \frac{n^{n/2}}{2^{n/2}}
$
so
$\frac{n!}{2^n} \ge \frac{n^{n/2}}{2^{3n/2}}
= (n/2^3)^{n/2}
= (n/8)^{n/2}
$.
If $n > 8m$,
$\frac{n!}{2^n}> m^{4m}$,
so by choosing $m$ (and therefore $n$) large enough,
we can make $\frac{n!}{2^n}$
as large as we want.
To show that $n!/k^n$ gets arbitrarily large, for any real $k > 1$,
look at the $n/k$ values from $n(1-1/k)$ to $n$.
Then $n! >(n(1-1/k))^{n/k}$,
so, letting $c = 1-1/k$,
$$n!/k^n >\frac{(cn)^{n/k}}{k^n}
= \big(\frac{(cn)^{1/k}}{k}\big)^n
= \big(\frac{cn}{k^k}\big)^{n/k}
= (r n)^{n/k}
$$
where $r = c/(k^k) = (1-1/k)/(k^k)$
$.
Again, by making $n$ large,
this can be made arbitrarily large.
