Función polilogarítmica

En matemáticas, una función polilogarítmica^[1]​ en n es un polinomio formado a partir del logaritmo de n, es decir:

${\displaystyle a_{k}(\log n)^{k}+a_{k-1}(\log n)^{k-1}+\cdots +a_{1}(\log n)+a_{0}.}$

La notación log^kn se utiliza a menudo como forma concisa para (log n)^k, análoga a sin²θ para (sin θ)².

En ciencias de la computación, las funciones polilogarítmicas se dan como orden de magnitud del tiempo de cálculo necesario para algunas operaciones de estructura de datos. Además, la función exponencial de una función polilogarítmica produce una función con crecimiento casi polinómico, y se dice que los algoritmos con esta complejidad temporal requieren tiempo casi polinómico.^[2]​

Todas las funciones polilogarítmicas de n son o(n^ε) para cada exponente ε > 0 (para el significado de este símbolo, consúltese cota superior asintótica), es decir, una función polilogarítmica crece más lentamente que cualquier exponente positivo. Esta observación es la base de la notación O débil Õ(n).^[3]​