http://debianws.lexgopc.com/wiki143/index.php?action=history&feed=atom&title=Polylogarithmic_functionPolylogarithmic function - Revision history2026-10-26T19:07:11ZRevision history for this page on the wikiMediaWiki 1.43.1http://debianws.lexgopc.com/wiki143/index.php?title=Polylogarithmic_function&diff=277735&oldid=previmported>David Eppstein: steal references from big O notation and Quasi-polynomial time2024-05-15T04:27:41Z<p>steal references from <a href="/wiki143/index.php?title=Big_O_notation" title="Big O notation">big O notation</a> and <a href="/wiki143/index.php?title=Quasi-polynomial_time" title="Quasi-polynomial time">Quasi-polynomial time</a></p>
<p><b>New page</b></p><div>{{Short description|Polynomial function with logarithm terms}}<br />
{{Distinguish|Polylogarithm}}<br />
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><br />
<br />
: <math>a_k (\log n)^k + a_{k-1} (\log n)^{k-1} + \cdots + a_1(\log n) + a_0. </math><br />
<br />
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}}}}.<br />
<br />
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><br />
<br />
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><br />
<br />
== References ==<br />
{{reflist}}<br />
<br />
[[Category:Mathematical analysis]]<br />
[[Category:Polynomials]]<br />
[[Category:Analysis of algorithms]]<br />
<br />
<br />
{{mathanalysis-stub}}<br />
{{polynomial-stub}}</div>imported>David Eppstein