Polylogarithmic function

A polylogarithmic function in n is a polynomial in the logarithm of n,

${\displaystyle a_{k}(\log n)^{k}+\cdots +a_{1}(\log n)+a_{0}.}$

The notation ${\displaystyle \log ^{k}n}$ is often used as a shorthand for ${\displaystyle (\log n)^{k}}$, analogous to ${\displaystyle \sin ^{2}\theta }$ for ${\displaystyle (\sin \theta )^{2}}$.

In computer science, polylogarithmic functions occur as the order of time or memory used by some algorithms (e.g., "it has polylogarithmic order").

All polylogarithmic functions of ${\displaystyle n}$ are ${\displaystyle o(n^{\varepsilon })}$ 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

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