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 Template:Math is often used as a shorthand for Template:Math, analogous to Template:Math for Template:Math.

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 Template:Math for every exponent Template:Math (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 Template:Math.

References

Template:Asbox Template:Polynomial-stub