Polylogarithmic function

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

${\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]

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

• v
• t
• e

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

• v
• t
• e