Jump to content

Polylogarithmic function

From Wikipedia, the free encyclopedia

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.