Polylogarithmic function

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 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. 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).

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,^[1]

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 log^kn is often used as a shorthand for (log n)^k, 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.^[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.

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

• v
• t
• e

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

• v
• t
• e