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

Question

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$)?

Answer 1

$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.