patternMinor
Useful functions between polylogarithmic and polynomial?
Viewed 0 times
polylogarithmicpolynomialbetweenusefulandfunctions
Problem
I'm wondering if there are any useful functions asymptotically greater than a polylogarithmic function and less than a polynomial function.
That is, a function $f(n)$ such that
$f(n) = \omega(\log(n)^k)$ for some constant $k > 0$
and
$f(n) = o(n^k)$ for some constant $k > 0$
What I mean by useful, is that it was used in a proof, algorithm, etc. rather than simply producing a function to fit these restrictions.
That is, a function $f(n)$ such that
$f(n) = \omega(\log(n)^k)$ for some constant $k > 0$
and
$f(n) = o(n^k)$ for some constant $k > 0$
What I mean by useful, is that it was used in a proof, algorithm, etc. rather than simply producing a function to fit these restrictions.
Solution
According to Wikipedia (which attributes the following result to Knuth), the running time of the mixed-level Toom–Cook algorithm for integer multiplication is
$$ \Theta(n\log n \cdot 2^{\sqrt{2\log n}}). $$
The function $2^{\sqrt{2\log n}}$ is super-polylogarithmic but sub-polynomial.
$$ \Theta(n\log n \cdot 2^{\sqrt{2\log n}}). $$
The function $2^{\sqrt{2\log n}}$ is super-polylogarithmic but sub-polynomial.
Context
StackExchange Computer Science Q#74613, answer score: 7
Revisions (0)
No revisions yet.