0
$\begingroup$

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

  • 0
    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.2012-07-10
  • 0
    n! grows like $n^{n}$ http://en.wikipedia.org/wiki/Stirling%27s_formula2012-07-10

1 Answers 1

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.