1
$\begingroup$

We know that:

  • $k^n = o(n!)$
  • $n! = o(n^n)$

where $o$ refers to "little o notation" (i.e. bounds that are asymptotically not tight).

With that in mind:

  • Are there any defined or academically established classes for problems with complexity of at most $O(n!)$ and $O(n^n)$?
  • What is the set relationship for these classes of problems with respect to $\mathsf{EXPTIME}$ or e.g. $\mathsf{2\mbox{-}EXPTIME}$?
$\endgroup$
1
$\begingroup$

$\mathsf{EXPTIME}$ is the class of problems solvable by algorithms whose running time is $O(2^{n^c})$ for some $c>0$. In contrast, $\mathsf{E}$ is the class of problems solvable by algorithms whose running time is $O(2^{cn})$ for some $c>0$.

These definitions show that problems solvable in time $O(n!)$ or $O(n^n)$ are in $\mathsf{EXPTIME}$, but not necessarily in $\mathsf{E}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.