L-notation is anasymptotic notation analogous tobig-O notation, denoted as${\displaystyle L_n[\alpha ,c]}$ for abound variable${\displaystyle n}$tending to infinity. Like big-O notation, it is usually used to roughly convey the rate of growth of afunction, such as thecomputational complexity of a particularalgorithm.

It is defined as

${\displaystyle L_n[\alpha ,c]=e^{(c+o(1))(\ln n{)}^{\alpha }(\ln \ln n{)}^{1-\alpha }}}$

wherec is a positive constant, and${\displaystyle \alpha }$ is a constant${\displaystyle 0\le \alpha \le 1}$.

L-notation is used mostly incomputational number theory, to express the complexity of algorithms for difficultnumber theory problems, e.g.sieves forinteger factorization and methods for solvingdiscrete logarithms. The benefit of this notation is that it simplifies the analysis of these algorithms. The${\displaystyle e^{c(\ln n{)}^{\alpha }(\ln \ln n{)}^{1-\alpha }}}$ expresses the dominant term, and the${\displaystyle e^{o(1)(\ln n{)}^{\alpha }(\ln \ln n{)}^{1-\alpha }}}$ takes care of everything smaller.

When${\displaystyle \alpha }$ is 0, then

${\displaystyle L_n[\alpha ,c]=L_n[0,c]=e^{(c+o(1))\ln \ln n}=(\ln n{)}^{c+o(1)}}$

is apolylogarithmic function (apolynomial function of ln n);

When${\displaystyle \alpha }$ is 1 then

${\displaystyle L_n[\alpha ,c]=L_n[1,c]=e^{(c+o(1))\ln n}=n^{c+o(1)}}$

is a fullyexponential function of ln n (and thereby polynomial inn).

If${\displaystyle \alpha }$ is between 0 and 1, the function issubexponential of ln n (andsuperpolynomial).

Many general-purposeinteger factorization algorithms havesubexponential time complexities. The best is thegeneral number field sieve, which has an expected running time of

${\displaystyle L_n[1/3,c]=e^{(c+o(1))(\ln n{)}^{1/3}(\ln \ln n{)}^{2/3}}}$

for${\displaystyle c=(64/9{)}^{1/3}\approx 1.923}$. The best such algorithm prior to the number field sieve was thequadratic sieve which has running time

${\displaystyle L_n[1/2,1]=e^{(1+o(1))(\ln n{)}^{1/2}(\ln \ln n{)}^{1/2}}.}$

For theelliptic curvediscrete logarithm problem, the fastest general purpose algorithm is thebaby-step giant-step algorithm, which has a running time on the order of the square-root of the group ordern. InL-notation this would be

${\displaystyle L_n[1,1/2]=n^{1/2+o(1)}.}$

The existence of theAKS primality test, which runs inpolynomial time, means that the time complexity forprimality testing is known to be at most

${\displaystyle L_n[0,c]=(\ln n{)}^{c+o(1)}}$

wherec has been proven to be at most 6.^[1]

L-notation has been defined in various forms throughout the literature. The first use of it came fromCarl Pomerance in his paper "Analysis and comparison of some integer factoring algorithms".^[2] This form had only the${\displaystyle c}$ parameter: the${\displaystyle \alpha }$ in the formula was${\displaystyle 1/2}$ for the algorithms he was analyzing. Pomerance had been using the letter${\displaystyle L}$ (or lower case${\displaystyle l}$) in this and previous papers for formulae that involved many logarithms.

The formula above involving two parameters was introduced byArjen Lenstra andHendrik Lenstra in their article on "Algorithms in Number Theory".^[3] It was introduced in their analysis of adiscrete logarithm algorithm ofCoppersmith. This is the most commonly used form in the literature today.

The Handbook of Applied Cryptography defines the L-notation with a big${\displaystyle O}$ around the formula presented in this article.^[4] This is not the standard definition. The big${\displaystyle O}$ would suggest that the running time is an upper bound. However, for the integer factoring and discrete logarithm algorithms that L-notation is commonly used for, the running time is not an upper bound, so this definition is not preferred.

• Asymptotic analysis
• Computational complexity theory

• Articles with short description
• Short description matches Wikidata