Polylogarithmic

From Wikipedia, the free encyclopedia

This article does not cite any references or sources. (October 2006)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

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.

Not to be confused with polylogarithms.