# complexity for $f(x)=n!$ and O($2^n$)

Suppose that algorithm has O($n!$). We all know that $n!$ should be smaller than $2^{2^n}$, but bigger than $2^n$.

So, will O($n!$) be in EXPTIME (EXP)?

Will we able to write O($n!$) as O($2^n$)?

-
No -- $n!$ grows faster than $2^n$, and indeed faster than any exponential function. Also, EXPTIME is a class of problems -- its members are subsets of $\Sigma ^*$ (or of $\mathbb N$ or something like that, depending on you precise formalism). It does not contain anything of the form $O(...)$, since $O(...)$ denotes a class of functions rather than a set of finite symbol strings. –  Henning Makholm Jul 10 '12 at 11:33
n! grows like $n^{n}$ en.wikipedia.org/wiki/Stirling%27s_formula –  tulasi Jul 10 '12 at 11:59

$n!$ is not $O(2^n)$. The function $n\mapsto n!$ grows much faster that $n\mapsto 2^n$. It is possible for algorithms to be much worse than exponential time.
A perfect example of a $O(n!)$ algorithm is the mean time for the "bozo sort" in which you randomly sort a list of sortables, check if it is in order, and repeat if necessary.