Polylogarithmic function explained

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

a _{k} ( log n) ^{k} + a _{k-1} ( log n) ^{k-1} + … + a _{1(log} n) + a _{0.}

The notation is often used as a shorthand for, analogous to for .

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 are for every exponent (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 .^[2]

Notes and References

1. Web site: polylogarithmic. Black. Paul E.. 2004-12-17. U.S. National Institute of Standards and Technology. Dictionary of Algorithms and Data Structures. 2010-01-10.
2. Book: Cormen . Thomas H. . Introduction to Algorithms . Leiserson . Charles E. . Rivest . Ronald L. . Stein . Clifford . The MIT Press . 2022 . 9780262046305 . 4th . Cambridge, Mass. . 74–75 .