[Solved]: If $n^{\log n}$ is not polynomial or exponential, then what this function is called?

Problem Detail: 

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.

Asked By : user777

Answered By : Tom van der Zanden

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48124

3.2K people like this

 Download Related Notes/Documents