Polylogarithmic function

Not to be confused with Polylogarithm.

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_\ell(x) = o(x^\varepsilon)\,

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

References

  • E. Black, Paul (2004-12-17). "polylogarithmic". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Retrieved 2010-01-10. 


fonte: https://web.archive.org/web/20160314113235/https://en.wikipedia.org/wiki/Polylogarithmic_function