Misplaced Pages

Polylogarithmic function

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Polylogarithmic) Polynomial function with logarithm terms Not to be confused with Polylogarithm.

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 + ⋯ + a 1 ( log ⁡ n ) + a 0 . {\displaystyle a_{k}(\log n)^{k}+a_{k-1}(\log n)^{k-1}+\cdots +a_{1}(\log n)+a_{0}.}

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

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.

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

  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 Misplaced Pages by expanding it.

Stub icon

This polynomial-related article is a stub. You can help Misplaced Pages by expanding it.

Categories: