Polylogarithmique

 Ne doit pas être confondu avec Polylogarithme.

Une fonction polylogarithmique de n est polynomiale par rapport au logarithme de n. Elle a la forme suivante : $a_k \log^k(n) + \cdots + a_1 \log(n) + a_0.$

Propriétés

Une fonction polylogarithmique croît plus doucement que n'importe quel polynôme. Plus précisément, au voisinage de l'infini, toutes les fonctions polylogarithmiques sont négligeables par rapport aux fonctions puissance à n'importe quel exposant strictement positif :

$\forall \varepsilon \in \R^{+*} \quad P_l(x) = o(x^\varepsilon)\,$

Applications

En informatique, les fonctions polylogarithmiques apparaissent dans les complexités de certains algorithmes (et en particulier des algorithmes parallèles, dans les classes de complexité parallèle).