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}},<ref>{{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}}</ref>

: <math>a_k (\log n)^k + a_{k-1} (\log n)^{k-1} + \cdots + a_1(\log n) + a_0. </math>

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

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'')}}.<ref>{{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=}}</ref>

== References == {{reflist}}

Category:Mathematical analysis Category:Polynomials Category:Analysis of algorithms