En matemáticas , una función polilogarítmica en n es un polinomio en el logaritmo de n , [1]
La notación log k n se utiliza a menudo como una abreviatura de (log n ) k , análoga a sin 2 θ para (sin θ ) 2 .
En informática , las funciones polilogarítmicas se dan 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 cuasipolinómico , y se dice que los algoritmos con esta complejidad temporal toman un tiempo cuasipolinómico . [2]
Todas las funciones polilogarítmicas de n son o( n ε ) para cada 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]
