patternMinor
An algorithm that is $O(n^{\log(n)})$
Viewed 0 times
algorithmthatlog
Problem
After having searched for a while, and after having read this
https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities
I was just wondering: is there some example of algorithm whose time complexity is ?$$O(n^{\log(n)})$$
Sorry for the arid question, I would just like to know if there is some example, being this a function that grows faster than polynomials but slower than exponentials.
https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities
I was just wondering: is there some example of algorithm whose time complexity is ?$$O(n^{\log(n)})$$
Sorry for the arid question, I would just like to know if there is some example, being this a function that grows faster than polynomials but slower than exponentials.
Solution
Yes, there are examples, though I don't know of any elementary ones. Before I give one, notice that
$$
n^{\log n} = (2^{\log n})^{\log n} = 2^{(\log n)^2} = O(2^{\text{poly}(\log n)})
$$
where $\text{poly}$ is a polynomial function (in this case quadratic).
For this reason, the time complexity you are interested in ($n^{\log n}$) is an example of quasi-polynomial time (QP) - it's two to the power of a polynomial function of $\log n$.
Quasi-polynomial time is somewhat unusual to encounter, but by the time hierarchy theorem, we know that there are decision problems that require any complexity bound we might be interested in, including quasi-polynomial time. That includes that there must be problems that require $n^{\log n}$ (up to a logarithmic factor). But that doesn't mean that any of those examples is necessarily natural.
Perhaps the most famous examples of quasi-polynomial time algorithms are:
-
The best known algorithm for the graph isomorphism problem. The graph isomorphism problem is, on input two graphs $G_1$ and $G_2$, are $G_1$ and $G_2$ isomorphic? László Babai proposed an algorithm in 2017 which runs in quasipolynomial time.
-
The best known algorithm for the parity game problem, which has time $O(n^{\log n + 6})$. (See this paper.)
Neither of these algorithms is known to be asymptotically optimal.
$$
n^{\log n} = (2^{\log n})^{\log n} = 2^{(\log n)^2} = O(2^{\text{poly}(\log n)})
$$
where $\text{poly}$ is a polynomial function (in this case quadratic).
For this reason, the time complexity you are interested in ($n^{\log n}$) is an example of quasi-polynomial time (QP) - it's two to the power of a polynomial function of $\log n$.
Quasi-polynomial time is somewhat unusual to encounter, but by the time hierarchy theorem, we know that there are decision problems that require any complexity bound we might be interested in, including quasi-polynomial time. That includes that there must be problems that require $n^{\log n}$ (up to a logarithmic factor). But that doesn't mean that any of those examples is necessarily natural.
Perhaps the most famous examples of quasi-polynomial time algorithms are:
-
The best known algorithm for the graph isomorphism problem. The graph isomorphism problem is, on input two graphs $G_1$ and $G_2$, are $G_1$ and $G_2$ isomorphic? László Babai proposed an algorithm in 2017 which runs in quasipolynomial time.
-
The best known algorithm for the parity game problem, which has time $O(n^{\log n + 6})$. (See this paper.)
Neither of these algorithms is known to be asymptotically optimal.
Context
StackExchange Computer Science Q#159314, answer score: 9
Revisions (0)
No revisions yet.