Polylogarithmic function

A polylogarithmic function in n is a polynomial in the logarithm of n,

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

In computer science, polylogarithmic functions occur as the order of memory used by some algorithms (e.g., "it has polylogarithmic order").

All polylogarithmic functions are

$P_{l}(x)=o(x^{\epsilon })\,$

for every exponent ε > 0 (for the meaning of this symbol, see small o notation), that is, a polylogarithmic function grows slower than any positive exponent. This observation is the basis for the soft O notation.

Not to be confused with polylogarithms.

References

• Paul E. Black, "polylogarithmic", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004.