Función polilogarítmica

En matemáticas , una función polilogarítmica en n es un polinomio en el logaritmo de n , ^{[ 1 ]}

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

La notación log ^k n se usa a menudo como una forma abreviada de (log n ) ^k , análoga a sin ² θ para (sin θ ) ² .

En informática , las funciones polilogarítmicas aparecen como el orden de tiempo para algunas operaciones de estructuras de datos . Además, la función exponencial de una función polilogarítmica produce una función con crecimiento cuasipolinomial , y se dice que los algoritmos con esta complejidad temporal toman tiempo cuasipolinomial . ^{[ 2 ]}

Todas las funciones polilogarítmicas de n son o( n ^ε ) para todo exponente ε > 0 (para el significado de este símbolo, véase la notación o minúscula ), 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 suave Õ( n ) . ^{[ 3 ]}