$O(n^{\log(n)}) $ time algorithms

Question

Is $O(n^{\log(n)}) $ time algorithm considered of exponential time ?

Is it applicable ?

Answer 1

No, $O(n^{\log n})$ is not considered exponential time. It can be called either sub-exponential or super-polynomial time. Remember that exponential time is defined as

$$ \text{EXPTIME} = \bigcup_k \text{TIME}(2^{n^k}) $$

To see that $n^{\log n} = O(2^{n^k})$ for any $k \geq 1$, simply take the logarithm of both sides to get

$$ (\log n)^2 = O(n^k) $$

which is clearly true.

Answer 2

It is not exponential time, but it by no means is pretty in the sense that $n^{\log(n)}$ still become impractical to use for relatively small n. Factoring is known to exist in this complexity class.

To be more specific. If we define EXPTIME as taking time asymptotically bounded from top and bottom by two functions of the form

$e^{P(n)}$ for some polynomial P.

And if we define Polynomial Time as it's usual definition of being bounded polynomially, then the time you have mentioned (often called super polynomial time) exists within the region

$$e^{P(\log(n))}$$

Naturally we can get more specific divisions by considering classes of the form

$$e^{P(\log^k(n))}$$

Where the k denotes how many times the logarithm is iterated. k=0 is exponential time. k=1 is super polynomial time (the time class you mentioned) k=2 is also super polynomial yet asymptotically below the time you have presented, in other words a new time class that exists between polynomial and this one. And as K grows you get 'weaker' time classes that still trump polynomial time. Think of it like a tower of circles inside circles (inception like) where at the very center is an unreadable dot that is polynomial time and the outer circle exponential time and the time class you mentioned $n^{\log(n)}$ being the next ring in this infinitely long sequence of nested circles

Hopefully that gave a good image :)