Editing 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 [[Big O notation|order]] of [[time complexity|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#Extensions to the Bachmann–Landau notations|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]]


{{mathanalysis-stub}}
{{polynomial-stub}}