Encyclopedia

Polylogarithmic function

Polynomial function with logarithm terms

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated May 15, 2024

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}+\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.

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

Watch videos about Polylogarithmic functionExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Polylogarithmic function”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.