I just found this sentence on page 6 of Garey and Johnson's "Computers and Intractability".

Any algorithm whose time complexity function cannot be so bounded is called an exponential time algorithm (although it should be noted that this definition includes certain non-polynomial time complexity functions, like $n^{\log n}$, which are not normally regarded as exponential functions).

My question as following,

If $n^{\log n}$ is not polynomial nor exponential, then what this function is called? Does this have a name or special cases or not?

Thank you.


1 Answer 1


There is no fixed terminology for these types of functions. You might sometimes see "subexponential" or "superpolynomial" used to refer to this kind of behavior.

  • 9
    $\begingroup$ Another common term is quasipolynomial. $\endgroup$ Oct 11, 2015 at 19:42
  • 3
    $\begingroup$ @user777 I think subexponential is of form $$c^{n^{\frac1{1+\gamma}}}$$ while superpolynomial or quasipolynomial is of form $$c^{\log^{1+\gamma} n}$$ with $c,\gamma>0$ remaining fixed $\endgroup$
    – user39969
    Nov 21, 2015 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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