Fonctions utiles entre polylogarithmique et polynôme?

Je me demande s'il existe des fonctions utiles asymptotiquement supérieures à une fonction polylogarithmique et inférieures à une fonction polynomiale.

Autrement dit, une fonction $f(n)$ tel que

$f(n) = \omega(\log(n)^k)$ pour une constante $k > 0$

et

$f(n) = o(n^k)$ pour une constante $k > 0$

Ce que je veux dire par utile, c'est qu'il a été utilisé dans une preuve, un algorithme, etc. plutôt que de simplement produire une fonction pour s'adapter à ces restrictions.

Selon Wikipedia (qui attribue le résultat suivant à Knuth), le temps d'exécution de l'algorithme Toom – Cook à plusieurs niveaux pour la multiplication des nombres entiers est

$$\Theta(n\log n \cdot 2^{\sqrt{2\log n}}).$$ La fonction $2^{\sqrt{2\log n}}$ est super-polylogarithmique mais sous-polynomial.