Polylogarithmic function: Difference between revisions

Content deleted Content added

Inline

Revision as of 05:44, 4 July 2022

In mathematics, a polylogarithmic function in $n$ is a polynomial in the logarithm of $n$ ,

a_{k}(\log n)^{k}+a_{k-1}(\log n)^{k-1}+\cdots +a_{1}(\log n)+a_{0}.

The notation $log k n$ is often used as a shorthand for $(log n) k$ , analogous to $sin 2 θ$ for $(sin θ) 2$ .

In computer science, polylogarithmic functions occur as the order of time or memory used by some algorithms (e.g., "it has polylogarithmic order").

All polylogarithmic functions of $n$ are $O(n ε)$ for every exponent $ε > 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 $Õ(n)$ .

References

Black, Paul E. (2004-12-17). "polylogarithmic". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Retrieved 2010-01-10.

This mathematical analysis–related article is a stub. You can help Wikipedia by expanding it.

P ≟ NP

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

@@ Line 1: / Line 1: @@
+{{Short description|Polynomial function with logarithm terms}}
 {{Distinguish|Polylogarithm}}
-A '''polylogarithmic function''' in ''n'' is a [[polynomial]] in the [[logarithm]] of ''n'',
+In [[mathematics]], a '''polylogarithmic function''' in {{mvar|n}} is a [[polynomial]] in the [[logarithm]] of {{mvar|n}},
-: <math>a_k (\log n)^k + \cdots + a_1(\log n) + a_0. </math>
-The notation <math>\log^k n</math> is often used as a shorthand for <math>(\log n)^k</math>, analogous to <math>\sin^2 \theta</math> for <math>(\sin \theta)^2</math>.
+: <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]] or [[space complexity|memory used]] by some [[algorithm]]s (e.g., "it has polylogarithmic order").
-All polylogarithmic functions  of <math>n</math> are <math>o(n^\varepsilon)</math> for every exponent ''&epsilon;''&nbsp;>&nbsp;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]] Õ(''n'').
+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'')}}.
 == References ==