Polylogarithmic function

Template:Short description In mathematics, a polylogarithmic function in Template:Mvar is a polynomial in the logarithm of Template:Mvar,

$a_k(\log n{)}^k+a_{k-1}(\log n{)}^{k-1}+\cdots +a_1(\log n)+a_0.$

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 for some data structure operations. Additionally, the exponential function of a polylogarithmic function produces a function with quasi-polynomial growth, and algorithms with this as their time complexity are said to take quasi-polynomial time.

All polylogarithmic functions of Template:Mvar 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).

References

Template:Asbox Template:Polynomial-stub