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}+\cdots +a_{1}(\log n)+a_{0}.

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

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

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

If a function is bounded by an exponential function of a polylogarithmic function, it is said to exhibit quasi-polynomial growth. This is used in computational complexity theory to define quasi-polynomial time and quasi-polynomial bounds on other complexity measures.

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.