Polylogarithmic function

Short description: Polynomial function with logarithm terms

In mathematics, a polylogarithmic function in n is a polynomial in the logarithm of n,

[math]\displaystyle{ a_k (\log n)^k + a_{k-1} (\log n)^{k-1} + \cdots + a_1(\log n) + a_0. }[/math]

The notation log^kn is often used as a shorthand for (log n)^k, analogous to sin²θ for (sin θ)².

In computer science, polylogarithmic functions occur as the order of time or memory used by some algorithms (e.g., "it has polylogarithmic order"), such as in the definition of QPTAS (see PTAS).

All polylogarithmic functions of n are o(n^ε) 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).

If a function is bounded by an exponential function of a polylogarithmic function, it is said to exhibit quasi-polynomial growth. This is used in computational complexity theory to define quasi-polynomial time and quasi-polynomial bounds on other complexity measures.

References

• Black, Paul E. (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.