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$


$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.


1 Answer 1


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.


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.