L-notation is an asymptotic notation analogous to big-O notation, denoted as L n [ α , c ] {\displaystyle L_{n}[\alpha ,c]} for a bound variable n {\displaystyle n} tending to infinity. Like big-O notation, it is usually used to roughly convey the rate of growth of a function, such as the computational complexity of a particular algorithm.
Definition It is defined as
L n [ α , c ] = e ( c + o ( 1 ) ) ( ln n ) α ( ln ln n ) 1 − α {\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}
where c is a positive constant, and α {\displaystyle \alpha } is a constant 0 ≤ α ≤ 1 {\displaystyle 0\leq \alpha \leq 1} . L-notation is used mostly in computational number theory, to express the complexity of algorithms for difficult number theory problems, e.g. sieves for integer factorization and methods for solving discrete logarithms. The benefit of this notation is that it simplifies the analysis of these algorithms. The e c ( ln n ) α ( ln ln n ) 1 − α {\displaystyle e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}} expresses the dominant term, and the e o ( 1 ) ( ln n ) α ( ln ln n ) 1 − α {\displaystyle e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}} takes care of everything smaller. When α {\displaystyle \alpha } is 0, then
L n [ α , c ] = L n [ 0 , c ] = e ( c + o ( 1 ) ) ln ln n = ( ln n ) c + o ( 1 ) {\displaystyle L_{n}[\alpha ,c]=L_{n}[0,c]=e^{(c+o(1))\ln \ln n}=(\ln n)^{c+o(1)}\,}
is a polylogarithmic function (a polynomial function of ln n); When α {\displaystyle \alpha } is 1 then
L n [ α , c ] = L n [ 1 , c ] = e ( c + o ( 1 ) ) ln n = n c + o ( 1 ) {\displaystyle L_{n}[\alpha ,c]=L_{n}[1,c]=e^{(c+o(1))\ln n}=n^{c+o(1)}\,}
is a fully exponential function of ln n (and thereby polynomial in n). If α {\displaystyle \alpha } is between 0 and 1, the function is subexponential of ln n (and superpolynomial).
Examples Many general-purpose integer factorization algorithms have subexponential time complexities. The best is the general number field sieve, which has an expected running time of
L n [ 1 / 3 , c ] = e ( c + o ( 1 ) ) ( ln n ) 1 / 3 ( ln ln n ) 2 / 3 {\displaystyle L_{n}[1/3,c]=e^{(c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}}}
… excerpt ends here. Continue reading the full article.
