Not to be confused with Polylogarithm.

In mathematics, a polylogarithmic function in n is a polynomial in the logarithm of n,[1]

The notation logkn is often used as a shorthand for (log n)k, analogous to sin2θ for (sin θ)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.[2]

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).[3]

References

edit
  1. ^ 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.
  2. ^ Complexity Zoo: Class QP: Quasipolynomial-Time
  3. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). Introduction to Algorithms (4th ed.). Cambridge, Mass.: The MIT Press. pp. 74–75. ISBN 9780262046305.


Stub icon

This mathematical analysis–related article is a stub. You can help Wikipedia by adding missing information.

Stub icon

This polynomial-related article is a stub. You can help Wikipedia by adding missing information.

📚 Artikel Terkait di Wikipedia

Taylor series

of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the

Polylogarithm

Lerch transcendent. Polylogarithms should not be confused with polylogarithmic functions, nor with the offset logarithmic integral Li(z), which has the

L-notation

c]=e^{(c+o(1))\ln \ln n}=(\ln n)^{c+o(1)}\,} is a polylogarithmic function (a polynomial function of ln n); When α {\displaystyle \alpha } is 1 then

Big O notation

science is O ~ {\displaystyle {\tilde {O}}} (read soft-O), which hides polylogarithmic factors. There are two definitions in use: some authors use f ( n )

Clausen function

particularly in relation to the evaluation of many classes of logarithmic and polylogarithmic integrals, both definite and indefinite. They also have numerous applications

Time complexity

algorithm gets closer to the target word. An algorithm is said to run in polylogarithmic time if its time T ( n ) {\displaystyle T(n)} is O ( ( log ⁡ n ) k

Quasi-polynomial growth

is bounded by an exponential function of a polylogarithmic function. This generalizes the polynomials and the functions of polynomial growth, for which

PolyL

machine by an algorithm whose space complexity is bounded by a polylogarithmic function in the size of the input. In other words, polyL = DSPACE((log n)O(1))