Funções úteis entre polilogarítmico e polinomial?

Gostaria de saber se existem funções úteis assintoticamente maiores que uma função polilogarítmica e menos que uma função polinomial.

Ou seja, uma função tal que$f(n)$

$f(n) = \omega(\log(n)^k)$ para alguma constante$k > 0$

e

$f(n) = o(n^k)$ para alguma constante$k > 0$

O que quero dizer com útil, é que ele foi usado em uma prova, algoritmo etc. em vez de simplesmente produzir uma função para atender a essas restrições.

De acordo com a Wikipedia (que atribui o seguinte resultado a Knuth), o tempo de execução do algoritmo Toom – Cook em nível misto para multiplicação de números inteiros é A função é super-polilogarítmica, mas sub-polinomial.

$$\Theta(n\log n \cdot 2^{\sqrt{2\log n}}).$$ $2^{\sqrt{2\log n}}$