0

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

Zat Mack
  • 575
  • 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. – hmakholm left over Monica Jul 10 '12 at 11:33
  • n! grows like $n^{n}$ http://en.wikipedia.org/wiki/Stirling%27s_formula – tulasi Jul 10 '12 at 11:59

1 Answers1

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.

ncmathsadist
  • 49,383