Poly-Exponential time complexity. Where $f(x) = n^n$

Are there any algorithms which have this time complexity.

Please list them if they exist. I coined the term myself, and a Google search turned nothing.

  • 3
    $\begingroup$ "Are there any algorithms that have this time complexity". Yes - one can construct generic algorithms. For instance, the algorithm that counts the number of strings formed from $n$ distinct symbols by enumerating them works in time $n^n$. You shouldn't expect useful algorithms with complexity $n^n$ to be well-studied, as it's too slow. $\endgroup$ – davidlowryduda Nov 17 '16 at 16:26
  • $\begingroup$ So $\sum{^n_{i=0} nPi} = n^n$ ? Can I please get a proof of this? $\endgroup$ – Tobi Alafin Nov 18 '16 at 8:55

The number of permutations of $n$ distinct items is $n! \sim \sqrt{2\pi} n^{n+1/2} e^{-n}$, so consider an algorithm that enumerates all these permutations and spends at most $e^n/\sqrt{n}$ time on each one.


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.