# Polylogarithmic function

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Polylogarithmic_function
> Markdown URL: https://mediated.wiki/source/Polylogarithmic_function.md
> Source: https://en.wikipedia.org/wiki/Polylogarithmic_function
> Source revision: 1223916470
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Polynomial function with logarithm terms}}
{{Distinguish|Polylogarithm}}
In [mathematics](/source/mathematics), a '''polylogarithmic function''' in {{mvar|n}} is a [polynomial](/source/polynomial) in the [logarithm](/source/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](/source/shorthand) for {{math|(log ''n''){{sup|''k''}}}}, analogous to {{math|sin{{sup|2}}''θ''}} for {{math|(sin ''θ''){{sup|2}}}}.

In [computer science](/source/computer_science), polylogarithmic functions occur as the [order](/source/Big_O_notation) of [time](/source/time_complexity) for some [data structure](/source/data_structure) operations. Additionally, the [exponential function](/source/exponential_function) of a polylogarithmic function produces a function with [quasi-polynomial growth](/source/quasi-polynomial_growth), and algorithms with this as their [time complexity](/source/time_complexity) are said to take [quasi-polynomial time](/source/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](/source/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](/source/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}}

---
Adapted from the Wikipedia article [Polylogarithmic function](https://en.wikipedia.org/wiki/Polylogarithmic_function) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Polylogarithmic_function?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.