The notation logkn is often used as a shorthand for (log n)k, analogous to sin2θ for (sin θ)2.
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.
- 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.