Polylogarithmic function

{{Short description|Polynomial function with logarithm terms}}

{{Distinguish|Polylogarithm}}

In mathematics, a polylogarithmic function in {{mvar|n}} is a polynomial in the logarithm of {{mvar|n}},{{cite web|url=http://xlinux.nist.gov/dads/HTML/polylogarith.html|title=polylogarithmic|last=Black|first=Paul E.|date=2004-12-17|publisher=U.S. National Institute of Standards and Technology|work=Dictionary of Algorithms and Data Structures|accessdate=2010-01-10}}

: $a\_k\; (\backslash log\; n)^k\; +\; a\_\{k-1\}\; (\backslash log\; n)^\{k-1\}\; +\; \backslash cdots\; +\; a\_1(\backslash log\; n)\; +\; a\_0.$

The notation {{math|log{{sup|k}}n}} is often used as a shorthand for {{math|(log n){{sup|k}}}}, analogous to {{math|sin{{sup|2}}θ}} for {{math|(sin θ){{sup|2}}}}.

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.{{ComplexityZoo|Class QP: Quasipolynomial-Time|Q#qp}}

All polylogarithmic functions of {{mvar|n}} are {{math|o(n{{sup|ε}})}} for every exponent {{math|ε > 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 {{math|Õ(n)}}.{{Cite book |last1=Cormen |first1=Thomas H. |url=https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ |title=Introduction to Algorithms |last2=Leiserson |first2=Charles E. |last3=Rivest |first3=Ronald L. |last4=Stein |first4=Clifford |publisher=The MIT Press |year=2022 |isbn=9780262046305 |edition=4th |location=Cambridge, Mass. |pages=74–75 |oclc= |url-access=}}