Polylogarithmic function

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, a polylogarithmic function in n is a <a href="/facts/Polynomial/Lzak8VVx">polynomial</a> in the <a href="/facts/Logarithm/QeXaV97q">logarithm</a> of n,

a
          
            k
          
        
        (
        log
        ⁡
        n
        
          )
          
            k
          
        
        +
        
          a
          
            k
            −
            1
          
        
        (
        log
        ⁡
        n
        
          )
          
            k
            −
            1
          
        
        +
        ⋯
        +
        
          a
          
            1
          
        
        (
        log
        ⁡
        n
        )
        +
        
          a
          
            0
          
        
        .
      
    
    {\displaystyle a_{k}(\log n)^{k}+a_{k-1}(\log n)^{k-1}+\cdots +a_{1}(\log n)+a_{0}.}

The notation logkn is often used as a <a href="/facts/Shorthand/LdCYfSu9">shorthand</a> for (log n)k, analogous to sin2θ for (sin θ)2.
In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, polylogarithmic functions occur as the <a href="/facts/Big_O_notation/weFFjSWg">order</a> of <a href="/facts/Time_complexity/77T62gmf">time</a> for some <a href="/facts/Data_structure/yNsNvL1I">data structure</a> operations. Additionally, the <a href="/facts/Exponential_function/ewlYxvR2">exponential function</a> of a polylogarithmic function produces a function with <a href="/facts/Quasi-polynomial_growth/UNKDGkqK">quasi-polynomial growth</a>, and algorithms with this as their <a href="/facts/Time_complexity/77T62gmf">time complexity</a> are said to take <a href="/facts/Quasi-polynomial_time/77T62gmf">quasi-polynomial time</a>.
All polylogarithmic functions of n are o(nε) for every exponent ε > 0 (for the meaning of this symbol, see <a href="/facts/Small_o_notation/weFFjSWg">small o notation</a>), that is, a polylogarithmic function grows more slowly than any positive exponent. This observation is the basis for the <a href="/facts/Soft_O_notation/weFFjSWg">soft O notation</a> Õ(n).

Polylogarithmic function open-in-new

Polylogarithmic function