Polylogarithmic function

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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

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


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