Polylogarithmic function
Template:Short description Template:Distinguish In mathematics, a polylogarithmic function in Template:Mvar is a polynomial in the logarithm of Template:Mvar,<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
- <math>a_k (\log n)^k + a_{k-1} (\log n)^{k-1} + \cdots + a_1(\log n) + a_0. </math>
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.<ref>Template:ComplexityZoo</ref>
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.<ref>Template:Cite book</ref>