14
$\begingroup$

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.

Improve this question
$\endgroup$
12
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 7
    $\begingroup$ Another common term is quasipolynomial. $\endgroup$ – Yuval Filmus Oct 11 '15 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 '15 at 20:46

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.