Polylogarithmic

Not to be confused with Polylogarithm.

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

$a_k \log^k(n) %2B \cdots %2B a_1 \log(n) %2B 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.

References

E. Black, Paul (2004-12-17). "polylogarithmic". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. http://xlinux.nist.gov/dads/HTML/polylogarith.html. Retrieved 2010-01-10.

‹The stub template below has been proposed for renaming to . See stub types for deletion to help reach a consensus on what to do.
Feel free to edit the template, but the template must not be blanked, and this notice must not be removed, until the discussion is closed. For more information, read the guide to deletion.›