({{, (RefLink[AsymptoticLess, paclet:ref/AsymptoticLess])[f,g,x->(SuperStar[x])] 
gives conditions for f(x)≺g(x) or f(x)∈o(g(x)) as x->(SuperStar[x]).}, {, (RefLink[AsymptoticLess, paclet:ref/AsymptoticLess])[f,g,{(Subscript[x, 1]),…,(Subscript[x, n])}->{(Subscript[x, 1]^( * )),…,(Subscript[x, n]^( * ))}]
gives conditions for f((Subscript[x, 1]),…,(Subscript[x, n]))≺g((Subscript[x, 1]),…,(Subscript[x, n])) or f((Subscript[x, 1]),…,(Subscript[x, n]))∈o(g((Subscript[x, 1]),…,(Subscript[x, n]))) as {(Subscript[x, 1]),…,(Subscript[x, n])}->{(Subscript[x, 1]^( * )),…,(Subscript[x, n]^( * ))}.}})

OpenersNotesSection(Spacer1)Details and Options

Asymptotic less is also expressed as f is little-o of g, f is of order less than g, f grows slower than g, and f is dominated by g. The point (SuperStar[x]) is often assumed from context.

Asymptotic less is an order relation and means (Abs[f(x)])≤c (Abs[g(x)]) when x is near (SuperStar[x]) for all constants c>0.

Typical uses include expressing simple strict upper bounds for functions and sequences near some point. It is frequently used for solutions to equations and to give simple strict upper bounds for computational complexity.

For a finite limit point (SuperStar[x]) and {(Subscript[x, 1]^( * )),…,(Subscript[x, n]^( * ))}:

For an infinite limit point:

(RefLink[AsymptoticLess, paclet:ref/AsymptoticLess])[f[x],g[x],x->(SuperStar[x])] exists if and only if (RefLink[Limit, paclet:ref/Limit])[(RefLink[Abs, paclet:ref/Abs])[f[x]/g[x]],x->(SuperStar[x])]==0 when g[x] does not have an infinite set of zeros near (SuperStar[x]).

The following options can be given:

Possible settings for (RefLink[Direction, paclet:ref/Direction]) include:

(RefLink[Direction, paclet:ref/Direction])->(RefLink[Exp, paclet:ref/Exp])[i θ] at (SuperStar[x]) indicates the direction tangent of a curve approaching the limit point (SuperStar[x]).

Possible settings for (RefLink[GenerateConditions, paclet:ref/GenerateConditions]) include:

Possible settings for (RefLink[PerformanceGoal, paclet:ref/PerformanceGoal]) include (RefLink[$PerformanceGoal, paclet:ref/$PerformanceGoal]), "Quality" and "Speed". With the "Quality" setting, (RefLink[Limit, paclet:ref/Limit]) typically solves more problems or produces simpler results, but it potentially uses more time and memory.

OpenersPrimaryExamplesSection(Spacer1)Examples  (49)

OpenersExampleSection0(Spacer1)Basic Examples  (2)

Verify that x≺(x^2) as x->∞:

AsymptoticLess[x,x^2,x->∞]

Visualize the two functions:

Plot[{x,x^2},{x,0,10},PlotLegends->"Expressions"]

Verify that x+y≺(x^2)+(y^2) as {x,y}->{∞,∞}:

AsymptoticLess[x+y,x^2+y^2,{x,y}->∞]

Visualize the two functions:

Plot3D[{x+y,x^2+y^2},{x,0,10},{y,0,10},PlotLegends->"Expressions"]

OpenersExampleSection1(Spacer1)Scope  (9)

Compare functions that are not strictly positive:

AsymptoticLess[x,-x^2,x->∞]

Show (1/x) diverges more slowly than (1/(x^2)) at the origin:

AsymptoticLess[(1/x),(1/(x^2)),x->0]

Answers may be Boolean expressions rather than explicit (RefLink[True, paclet:ref/True]) or (RefLink[False, paclet:ref/False]):

AsymptoticLess[Sinh[p(x-2)],Sin[x-2], x->2]

When comparing functions with parameters, conditions for the result may be generated:

AsymptoticLess[(1/(((x-1))^p)),(10/(x-1)), x->1]

By default, a two-sided comparison of the functions is made:

AsymptoticLess[(x^4),(x^2) UnitStep[x], x->0]

When comparing larger values of x, (x^4) is indeed smaller than (x^2) (UnitStepSeq[x]):

AsymptoticLess[(x^4),(x^2) UnitStep[x], x->0,Direction->"FromAbove"]

The relationship fails for smaller values of x:

AsymptoticLess[(x^4),(x^2) UnitStep[x], x->0,Direction->"FromBelow"]

Visualize the two functions:

Plot[{(x^4),(x^2)UnitStep[x]},{x,-1,1},PlotTheme->{"DashedLines","Detailed"}]

Functions like (RefLink[Sqrt, paclet:ref/Sqrt]) may have the same relationship in both real directions along the negative reals:

AsymptoticLess[(((Sqrt[z]-I))^3), (z+1),z->-1]

If approached from above in the complex plane, the same relationship is observed:

AsymptoticLess[(((Sqrt[z]-I))^3), (z+1),z->-1,Direction->-I]

However, approaching from below in the complex plane produces a different result:

AsymptoticLess[(((Sqrt[z]-I))^3), (z+1),z->-1,Direction->I]

This is due to a branch cut where the imaginary part of (RefLink[Sqrt, paclet:ref/Sqrt]) reverses sign as the axis is crossed:

TableForm[Table[{-1+Δ,Sqrt[-1+Δ],Abs[Sqrt[-1+Δ]-I]},{Δ,{0.01,-0.01,0.01I,-0.01I}}],TableHeadings->{None,{z,(Sqrt[z]),HoldForm@Abs[Sqrt[z]-I]}}]

Hence, the relationship does not hold in the complex plane in general:

AsymptoticLess[(((Sqrt[z]-I))^3), (z+1),z->-1,Direction->Complexes]

Visualize the relative sizes of the functions when approached from the four real and imaginary directions:

Plot[{Abs[ ((-1+Δz)/(((Sqrt[-1+Δz]-I))^3))],Abs[ ((-1+I Δz)/(((Sqrt[-1+I Δz]-I))^3))]},{Δz,-1,1},]

Compare multivariate functions:

AsymptoticLess[(((x-1))^2)(y-2), Sin[ x]Cos[3y/4],{x,y}->{1,2}]

Visualize the norms of the two functions:

Plot3D[{Abs[(((x-1))^2)(y-2)], Abs[Sin[ x]Cos[ 3y/2]]},{x,y}∈Disk[{1,2},.9],PlotTheme->"Detailed"]

Compare multivariate functions at infinity:

AsymptoticLess[ Exp[x]Log[y],x y,{x,y}->{-∞,∞}]

Use parameters when comparing multivariate functions:

AsymptoticLess[Sinh[x]y,Sinh[a x]y^n,{x,y}->{∞,1}]

OpenersExampleSection2(Spacer1)Options  (10)

OpenersExampleSubsection0(Spacer1)Assumptions  (1)

Specify conditions on parameters using (RefLink[Assumptions, paclet:ref/Assumptions]):

AsymptoticLess[1,x^a,x->0,Assumptions->a≥0]

Different assumptions can produce different results:

AsymptoticLess[1,x^a,x->0,Assumptions->a<0]

OpenersExampleSubsection1(Spacer1)Direction  (5)

Test the relation from below:

AsymptoticLess[x Sin[x],x UnitStep[x],x->0,Direction->"FromBelow"]

Equivalently:

AsymptoticLess[x Sin[x],x UnitStep[x],x->0,Direction->1]

Test the relation from above:

AsymptoticLess[x Sin[x],x UnitStep[x],x->0,Direction->"FromAbove"]

Equivalently:

AsymptoticLess[x Sin[x],x UnitStep[x],x->0,Direction->-1]

Test the relation at piecewise discontinuities:

AsymptoticLess[4Cos[x/2](x-2),FractionalPart[x^2]Sin[x],x->2,Direction->"FromBelow"]

AsymptoticLess[4Cos[x/2](x-2),FractionalPart[x^2]Sin[x],x->2,Direction->"FromAbove"]

Since it fails in one direction, the two-sided result is false as well:

AsymptoticLess[4Cos[x/2](x-2),FractionalPart[x^2]Sin[x],x->2,Direction->"TwoSided"]

Visualize the two functions and their ratio:

Plot[{4Cos[x/2](x-2),FractionalPart[x^2]Sin[x],Abs[4Cos[x/2](x-2)/FractionalPart[x^2]Sin[x]]},{x,1.5,2.5},PlotLegends->"Expressions"]

The relationship at a pole is independent of the direction of approach:

AsymptoticLess[Tan[x],((((2/(2x-π))))^2),x->π/2,Direction->"FromBelow"]

AsymptoticLessEqual[Tan[x],((((2/(2x-π))))^2),x->π/2,Direction->"FromAbove"]

AsymptoticLessEqual[Tan[x],((((2/(2x-π))))^2),x->π/2,Direction->(Reals)]

AsymptoticLessEqual[Tan[x],((((2/(2x-π))))^2),x->π/2,Direction->(Complexes)]

Test the relation at a branch cut:

AsymptoticLess[ Sqrt[x-1]-I,(Sqrt[Tanh[x]]),x->0,Direction->+I]

AsymptoticLess[ Sqrt[x-1]-I,(Sqrt[Tanh[x]]),x->0,Direction->-I]

AsymptoticLess[ Sqrt[x-1]-I,(Sqrt[Tanh[x]]),x->0,Direction->Reals]

AsymptoticLess[ Sqrt[x-1]-I,(Sqrt[Tanh[x]]),x->0,Direction->Complexes]

Compute the relation, approaching from different quadrants:

f[x_,y_] := Sin[x y]

g[x_,y_]:= x+Abs[y]

Approaching the origin from the first quadrant:

AsymptoticLess[f[x,y],g[x,y],{x,y}->{0,0},Direction->"FromAbove"]

Equivalently:

AsymptoticLess[f[x,y],g[x,y],{x,y}->{0,0},Direction->{"FromAbove","FromAbove"}]

Approaching the origin from the second quadrant:

AsymptoticLess[f[x,y],g[x,y],{x,y}->{0,0},Direction->{"FromBelow","FromAbove"}]

Approach the origin from the right half-plane:

AsymptoticLess[f[x,y],g[x,y],{x,y}->{0,0},Direction->{"FromAbove",Reals}]

Approaching the origin from the bottom half-plane:

AsymptoticLess[f[x,y],g[x,y],{x,y}->{0,0},Direction->{Reals,"FromBelow"}]

Visualize the ratio of the functions, which becomes small near the origin except along x==-y:

DensityPlot[Abs[f[x,y]/g[x,y]],{x,-1,1},{y,-1,1},PlotLegends->Automatic,ClippingStyle->Automatic]//Quiet

OpenersExampleSubsection2(Spacer1)GenerateConditions  (3)

Return a result without stating conditions:

AsymptoticLess[x^n,1,x->0,GenerateConditions->False]

This result is only valid if n>0:

AsymptoticLessEqual[x^n,1,x->0]

Return unevaluated if the results depend on the value of parameters:

AsymptoticLess[Exp[-a x],1,x->∞,GenerateConditions->None]

By default, conditions are generated that guarantee a result:

AsymptoticLess[Exp[-a x],1,x->∞]

By default, conditions are not generated if only special values invalidate the result:

AsymptoticLess[x y,(((x-a))^2)+(y^2),{x,y}->{0,0}]

With (RefLink[GenerateConditions, paclet:ref/GenerateConditions])->(RefLink[True, paclet:ref/True]), even these non-generic conditions are reported:

AsymptoticLess[x y,(((x-a))^2)+(y^2),{x,y}->{0,0},GenerateConditions->True]

OpenersExampleSubsection3(Spacer1)PerformanceGoal  (1)

Use (RefLink[PerformanceGoal, paclet:ref/PerformanceGoal]) to avoid potentially expensive computations:

f=2 y (z^2)-(z^3)+y (((x-2 y+3 z))^2)-z (((x-2 y+3 z))^2);
g=(y^2)-2 y z+(z^2)-y (x-2 y+3 z)+z (x-2 y+3 z)+(((x-2 y+3 z))^2);

AsymptoticLess[f,g,{x,y,z}->{0,0,0},PerformanceGoal->"Speed"]//AbsoluteTiming

The default setting uses all available techniques to try to produce a result:

AsymptoticEqual[f,g,{x,y,z}->{0,0,0}]//AbsoluteTiming

OpenersExampleSection3(Spacer1)Applications  (18)

OpenersExampleSubsection4(Spacer1)Basic Applications  (4)

Show that ⋯≺(x^3)≺(x^2)≺x≺1 at 0:

{AsymptoticLess[(x^3),(x^2),x->0],AsymptoticLess[(x^2),x,x->0],AsymptoticLess[(x^1),(x^0),x->0]}

Establish this symbolically:

AsymptoticLess[(x^k),(x^l),x->0,Assumptions->{k,l}∈(Integers) && k>l≥0]

Visualize the functions:

Plot[{1,Abs[x],Abs[(x^2)],Abs[(x^3)]},{x,-1,1},PlotLegends->"Expressions"]

This relationship extends to all real powers:

AsymptoticLess[(x^k),(x^l),x->0,Assumptions-> k>l]

Visualize functions with fractional and negative powers:

Plot[{Abs[1/x],Abs[1/(Sqrt[x])],1,Abs[(Sqrt[x])],Abs[x]},{x,-1,1},PlotLegends->"Expressions"]

Show that 1≺x≺(x^2)≺(x^3)≺⋯ at ∞:

{AsymptoticLess[1,x,x->∞],AsymptoticLess[x,(x^2),x->∞],AsymptoticLess[(x^2),(x^3),x->∞]}

Establish this symbolically:

AsymptoticLess[(x^k),(x^l),x->∞,Assumptions->{k,l}∈(Integers) && 0≤k<l]

Visualize the relationship in a logarithmic plot:

LogPlot[{1,Abs[x],Abs[(x^2)],Abs[(x^3)]},{x,10,100},PlotLegends->"Expressions"]

This relationship extends to all real powers:

AsymptoticLess[(x^k),(x^l),x->∞,Assumptions-> k<l]

Visualize functions with fractional and negative powers:

LogPlot[{Abs[1/x],Abs[1/(Sqrt[x])],1,Abs[(Sqrt[x])],Abs[x]},{x,10,100},PlotLegends->"Expressions"]

Show that (x^2) sin(1/x)≺x at 0:

AsymptoticLess[(x^2)Sin[1/x],x,x->0]

This relationship can be inferred from the fact that (Abs[(x^2) sin((1/x))])≤(x^2):

Plot[{Abs[(x^2)Sin[1/x]],Abs[x],(x^2)},{x,-2/3,2/3},PlotStyle->{Automatic,Automatic,Dashed},PlotLegends->"Expressions"]

Show that x≺(x^2) (sin(x)+2) at ∞:

AsymptoticLess[x,(x^2)(Sin[x]+2),x->∞]

LogPlot[{x,(x^2)(Sin[x]+2)},{x,1,100},PlotLegends->"Expressions"]

OpenersExampleSubsection5(Spacer1)Absolute and Relative Errors  (2)

A function (OverTilde[f])(x) approximates f(x) as x->(Subscript[x, 0]) with small absolute error if f(x)-(OverTilde[f])(x)≺1 as x->(Subscript[x, 0]). Show that 1 approximates exp(x) with small absolute error as x->0:

AsymptoticLess[Exp[x]-1,1,x->0]

Show that x+1 also approximates exp(x) with small absolute error as x->0:

AsymptoticLess[Exp[x]-(1+x),1,x->0]

Show that exp(x)/2 approximates cosh(x) with small absolute error as x->∞:

AsymptoticLess[Cosh[x]-Exp[x]/2,1,x->∞]

Show that exp(-x)/2 approximates cosh(x) with small absolute error as x->-∞:

AsymptoticLess[Cosh[x]-Exp[-x]/2,1,x->-∞]

A function (OverTilde[f])(x) approximates f(x) as x->(Subscript[x, 0]) with small relative error if f(x)-(OverTilde[f])(x)≺(OverTilde[f])(x) as x->(Subscript[x, 0]). Show that x+1 approximates exp(x) with small relative error as x->0:

AsymptoticLess[Exp[x]-(1+x),1+x,x->0]

Show that (1/(x^2)) approximates (1/(x^2))+(1/x) with small relative error as x->0:

AsymptoticLess[((1/x)+(1/(x^2)))-(1/(x^2)),(1/(x^2)),x->0]

But the preceding approximation does not have small absolute error:

AsymptoticLess[((1/x)+(1/(x^2)))-(1/(x^2)),1,x->0]

Similarly, Stirling's formula (Sqrt[2 π n]) ((((n/e)))^n) approximation to n! has small relative error as n->∞:

AsymptoticLess[n!-(Sqrt[2π n])(((n/E))^n),(Sqrt[2π n])(((n/E))^n),n->∞]

But not small absolute error:

AsymptoticLess[n!-(Sqrt[2π n])(((n/E))^n),1,n->∞]

OpenersExampleSubsection6(Spacer1)Asymptotic Approximation  (6)

Let f(x) be a function and (OverTilde[f])(x) an approximation to f(x) near (Subscript[x, 0]). Then the approximation is asymptotic if f(x)-(OverTilde[f])(x)≺(OverTilde[f])(x) at (Subscript[x, 0]). In other words, the remainder or error f(x)-(OverTilde[f])(x) is asymptotically smaller than the approximation. Show that 1 is an asymptotic approximation to (x^2)+x+1 at 0:

AsymptoticLess[((x^2)+x+1)-1,1,x->0]

Show that x+1 is an asymptotic approximation to (x^2)+x+1 at 0:

AsymptoticLess[((x^2)+x+1)-(x+1),x+1,x->0]

Show that 1.5` is not an asymptotic approximation to (x^2)+x+1 at 0:

AsymptoticLess[((x^2)+x+1)-1.5,1.5,x->0]

Show that Stirling's formula (Sqrt[2 π n]) ((((n/e)))^n) is an asymptotic approximation to n! as n->∞:

AsymptoticLess[n!-(Sqrt[2π n])(((n/E))^n),(Sqrt[2π n])(((n/E))^n),n->∞]

Show that x/log(x) is an asymptotic approximation to (PrimePi[x]) as x->∞:

AsymptoticLess[PrimePi[x]-x/Log[x],x/Log[x],x->∞]

(RefLink[Series, paclet:ref/Series]) generates asymptotic approximation to elementary and special functions. For instance, generate a degree-10 approximation to sin(x) at 0:

sin=Normal@Series[Sin[x],{x,0,10}]

Show that the series is asymptotic:

AsymptoticLess[Sin[x]-sin,sin,x->0]

Determine an asymptotic series of (RefLink[Cot, paclet:ref/Cot])[x] at 0:

cot=Normal@Series[Cot[x],{x,0,5}]

AsymptoticLess[Cot[x]-cot,cot,x->0]

Show that a series of (RefLink[Gamma, paclet:ref/Gamma])[x] is asymptotic at -1:

gamma=Normal@Series[Gamma[x],{x,-1,2}]

AsymptoticLess[Gamma[x]-gamma,gamma,x->-1]

Find an asymptotic approximation of ((log(sin(x)))^(1/3)) at 0:

expr=Normal@Series[((Log[Sin[x]])^(1/3)),{x,0,3}]

AsymptoticLess[((Log[Sin[x]])^(1/3))-expr,expr,x->0]

There can be subtleties with asymptotic approximation when the function to be approximated approaches zero infinitely many times in every neighborhood of the approximation point. As an example, consider the asymptotic expansion of (BesselJ[1, x]) near ∞:

besselJ=Normal@Series[BesselJ[1,x],{x,∞,2}]

The approximation is not asymptotic because at every zero of the Bessel function, the approximation is not quite zero:

{BesselJ[1,x],besselJ}/. x->BesselJZero[1,25]//N

Despite the ratio generally approaching zero, (Abs[J(1,x)-besselJ])≤c (Abs[besselJ]) is violated infinitely many times:

Plot[((besselJ-BesselJ[1,x])/besselJ),{x,1,40},PlotTheme->"Detailed",PlotPoints->200,PlotRange->0.003]

On the other hand, consider the approximation of the never-zero Hankel function (HankelH1[1, x]):

hankel1=Normal@Series[HankelH1[1,x],{x,∞,2}]//Expand

This approximation is asymptotic:

AsymptoticLess[HankelH1[1,x]-hankel1,hankel1,x->∞]

So is the approximation of the Hankel function of the second kind, (HankelH2[1, x]):

hankel2=Normal@Series[HankelH2[1,x],{x,∞,2}]//Expand

AsymptoticLess[HankelH2[1,x]-hankel2,hankel2,x->∞]//Quiet

As (BesselJ[1, x])==(1/2) ((HankelH1[1, x])+(HankelH2[1, x])), its approximation can be understood as nearly asymptotic, being the sum of two such approximations:

FullSimplify[besselJ==((hankel1+hankel2)/2)]

Alternatively, consider the asymptotic approximation of 1+(BesselJ[1, x]) near ∞:

besselJP1=Normal@Series[1+BesselJ[1,x],{x,∞,2}]//Expand

This is a true asymptotic approximation:

AsymptoticLess[1+BesselJ[1,x]-besselJP1,besselJP1,x->∞]

The limit of the ratio of the approximation and the function approaches 1 consistently:

Plot[Abs[((1+BesselJ[1,x]-besselJP1)/besselJP1)],{x,1,40},PlotTheme->"Detailed"]

Use (RefLink[AsymptoticIntegrate, paclet:ref/AsymptoticIntegrate]) to generate asymptotic approximations to definite integrals. For instance, find an asymptotic approximation to (∫_0^1)(e^(t x))dt as x->0 and compare to the exact value:

{approx,exact}={AsymptoticIntegrate[E^(t x),{t,0,1},{x,0,3}] ,Integrate[E^(t x), {t,0,1}]}

AsymptoticLess[exact-approx,approx,x->0]

Create an asymptotic approximation with a smaller number of terms:

approx2=AsymptoticIntegrate[E^(t x),{t,0,1},{x,0,1}]

This approximation is asymptotic to the exact integral as well as the first approximation:

AsymptoticLess[exact-approx2,approx2,x->0]

AsymptoticLess[approx-approx2,approx2,x->0]

Use (RefLink[AsymptoticIntegrate, paclet:ref/AsymptoticIntegrate]) to generate asymptotic approximations to indefinite integrals, though there is a need to account for the constant of integration. Consider an approximation of ∫sin(x)dx as x->0:

{approx,exact}={AsymptoticIntegrate[Sin[x],x,{x,0,3}],Integrate[Sin[x],x]}

Show that the approximation is asymptotic:

AsymptoticLess[exact-approx,approx,x->0]

However, the approximation is asymptotic after matching values at the expansion point:

AsymptoticLess[exact-approx -(exact-approx/.x->0),approx,x->0]

Compute two different asymptotic approximations of ∫(x^x)dx as x->0:

approx2=AsymptoticIntegrate[(x^x),x,{x,0,2}]

approx1=AsymptoticIntegrate[(x^x),x,{x,0,1}]

There is no symbolic result to compare to, but the process can be shown to be asymptotic:

AsymptoticLess[approx2-approx1,approx1,x->0]

Use (RefLink[AsymptoticDSolveValue, paclet:ref/AsymptoticDSolveValue]) to generate asymptotic approximations to a differential equation:

deqn={y''[x]-(x^4+E^x Sin[x]) y[x]==0==0,y[0]==0,y'[0]==2};

approx=AsymptoticDSolveValue[deqn,y[x],{x,0,8}]

There is no exact result to compare to, but the process can be shown to be asymptotic:

approx2=AsymptoticDSolveValue[deqn,y[x],{x,0,12}]

AsymptoticLess[approx2-approx,approx,x->0]

Compare with the values of a numerical solution obtained using (RefLink[NDSolveValue, paclet:ref/NDSolveValue]):

nsol=NDSolveValue[deqn,y[x],{x,0,0.5}]

Table[nsol-approx2,{x,0,0.5,0.1}]

OpenersExampleSubsection7(Spacer1)Asymptotic Scales & Series  (2)

A sequence of functions {(Subscript[ϕ, 1])(x),(Subscript[ϕ, 2])(x),…} is an asymptotic scale at (Subscript[x, 0]) iff (Subscript[ϕ, n+1])(x)≺(Subscript[ϕ, n])(x) at (Subscript[x, 0]). Write a function that can check whether a finite list of functions is an asymptotic scale:

AsymptoticScaleQ[list_,x_->x0_,o:OptionsPattern[]]:=BlockMap[AsymptoticLess[#[[2]],#[[1]],x->x0,o]&,list,2,1]

Integer powers give an asymptotic scale x at 0, with (RowWithSeparators[≻, "≻", (1/(x^3)), (1/(x^2)), (1/x), 1, x, (x^2), (x^3)]) as x->0:

AsymptoticScaleQ[{1/(x^3),1/(x^2),1/x,1,x,x^2,x^3},x->0]

They also form an asymptotic scale at ∞, but in the opposite order:

AsymptoticScaleQ[{(x^3),(x^2),x,1,(1/x),(1/(x^2)),(1/(x^3))},x->∞]

Powers of log(x) form an asymptotic scale, with (RowWithSeparators[≻, "≻", 1, (1/(log(x))), (1/((log^2)(x))), (1/((log^3)(x)))]) as x->∞:

AsymptoticScaleQ[{1,1/Log[x],1/((Log[x])^2),1/((Log[x])^3)},x->∞]

Form an asymptotic scale using (x^k) and log(x), with (RowWithSeparators[≻, "≻", 1, x, (x^2) log(x), (x^2), (x^3) log(x), (x^3), (x^4) log(x)]) as x->(SuperPlus[0]):

AsymptoticScaleQ[{1,x,(x^2) Log[x],(x^2),(x^3)Log[x],(x^3),(x^4)Log[x]},x->0,Direction->-1]

Show that exp(x) (x^(Subscript[α, 1]))≻exp(x) (x^(Subscript[α, 2]))≻exp(x) (x^(Subscript[α, 2]))≻⋯ as x->∞ if (Subscript[α, 1])<(Subscript[α, 2])<(Subscript[α, 3])<⋯:

Table[Exp[x](x^(-α)),{α,Sort[RandomReal[10,5]]}]

AsymptoticScaleQ[%,x->∞]

Write a function that sorts functions by the asymptotic ordering at some point (Subscript[x, 0]):

AsymptoticSort[list_List,x_->x0_,o:OptionsPattern[]]:=
Sort[list,AsymptoticLess[#1,#2,x->x0,o]&]

Generate a random list of integer power functions:

pows=RandomSample[Table[(x^i),{i,-3,3}]]

Asymptotically sort the list at 0:

AsymptoticSort[pows,x->0]

LogPlot[Evaluate[Abs[%]],{x,-1/2,1/2},PlotLegends->"Expressions"]

Asymptotically sort the same list at ∞:

AsymptoticSort[pows,x->∞]

LogPlot[Evaluate[Abs[%]],{x,10,100},PlotLegends->"Expressions"]

OpenersExampleSubsection8(Spacer1)Computational Complexity  (4)

Simple sorting algorithms (bubble sort, insertion sort) take approximately a (n^2) steps to sort n objects, while optimal general algorithms (heap sort, merge sort) take approximately b n (RefLink[Log, paclet:ref/Log])[n] steps to do the sort. Show that optimal algorithms always take less time to sort large enough collections of objects:

AsymptoticLess[b n Log[n], a (n^2),n->∞]

Certain special algorithms (counting sort, radix sort), where there is information ahead of time about the possible inputs, can run in c n time. These are even faster than the optimal algorithms when they can be used:

AsymptoticLess[c n, b n Log[n],n->∞]

Visualize the growth of the three time scales:

LogPlot[{(n^2),n Log[n],n},{n,10,1000},PlotLegends->"Expressions",PlotLabel->Row[{n∈o[n Log[n]],n Log[n]∈o[(n^2)]}, Spacer[10]]]

In a bubble sort, adjoining neighbors are compared and swapped if they are out of order. After one pass of n-1 comparisons, the largest element is at the end. The process is then repeated on remaining n-1 elements, and so forth, until only two elements at the very beginning remain. If comparison and swap takes c steps, the total number of steps for the sort is:

Sum[c(i-1),{i,n,2,-1}]

The polynomial is asymptotically approximated by just the quadratic term:

AsymptoticLess[(1/2) (-c n+c (n^2))-((c (n^2))/2),((c (n^2))/2),n->∞]

In a merge sort, the list of elements is split in two, each half is sorted, and then the two halves are combined. Thus, the time T[n] to do the sort will be the sum of some constant time b to compute the middle, 2T[n/2] to sort each half, and some multiple a n of the number of elements to combine the two halves:

reqn=T[n]==2T[n/2]+ a n +b

Solve the recurrence equation to find the time t to sort n elements:

t=RSolveValue[reqn, T[n],n]//Expand

This expression is asymptotically approximated by just the last term in the expression:

AsymptoticLess[t- n ((a Log[n])/(Log[2])),n((a Log[n])/(Log[2])), n->∞]

The traveling salesperson problem (TSP) consists of finding the shortest route connecting n cities. A naive algorithm is to try all n! routes. The Held–Karp algorithm improves that to roughly (n^2) (2^n) steps. Show that (n^2) (2^n)∈o(n!) and hence the Held–Karp algorithm is faster:

AsymptoticLess[n^2 (2^n),n!,n->∞]

Both algorithms show that the complexity class of TSP is no worse than EXPTIME, which are problems that can be solved in time (2^(p(n))). For Held–Karp, using p(n)==a n for some a>1 suffices:

AsymptoticLess[(n^2) (2^n),(2^(2n)),n->∞]

For the factorial, it is necessary to use a higher-degree polynomial, for example p(n)=(n^2):

AsymptoticLess[n!,(2^(n^2)),n->∞]

Approximate solutions can be found in (n^3) time, so the approximate TSP is in the complexity class P of problems solvable in polynomial time. Any polynomial algorithm is faster than an exponential one, or (n^k)∈o((2^n)):

AsymptoticLess[(n^k),(2^n),n->∞]

OpenersExampleSection4(Spacer1)Properties & Relations  (10)

(RefLink[AsymptoticLess, paclet:ref/AsymptoticLess]) is irreflexive, i.e. f(x)⊀f(x):

AsymptoticLess[f[x],f[x],x->x0]

It is transitive, i.e. f(x)≺g(x) and g(x)≺h(x) implies f(x)≺h(x):

{f,g,h}={x,(x^2),(x^3)};

{AsymptoticLess[f,g,x->∞],AsymptoticLess[g,h,x->∞],AsymptoticLess[f,h,x->∞]}

And it is antisymmetric, i.e. f(x)≺g(x) implies g(x)⊀f(x):

{f,g}={x,(x^2)};

{AsymptoticLess[f,g,x->∞],AsymptoticLess[g,f,x->∞]}

(RefLink[AsymptoticLess, paclet:ref/AsymptoticLess])[f[x],g[x],x->(Subscript[x, 0])] iff (RefLink[Limit, paclet:ref/Limit])[(RefLink[Abs, paclet:ref/Abs])[f[x]/g[x]],x->(Subscript[x, 0])]==0:

{f,g}={x,(x^2)};

{AsymptoticLess[f,g,x->∞],Limit[Abs[f/g],x->∞]}

{f,g}={(x^2),(x^3)/(1+x)};

{AsymptoticLess[f,g,x->∞],Limit[Abs[f/g],x->∞]}

In particular, the limit has to exist:

{f,g}={Sin[x],x Cos[x]};

{AsymptoticLess[f,g,x->∞],Limit[Abs[f/g],x->∞]}

If f(x)≺g(x), then f(x)⪯g(x):

{f,g}={x,(x^2)};

{AsymptoticLess[f,g,x->∞],AsymptoticLessEqual[f,g,x->∞]}

If f(x)≺g(x), then g(x)≻f(x):

{f,g}={x,(x^2)};

{AsymptoticLess[f,g,x->∞],AsymptoticGreater[g,f,x->∞]}

If f(x)≺g(x), then g(x)⪰f(x):

{f,g}={x,(x^2)};

{AsymptoticLess[f,g,x->∞],AsymptoticGreaterEqual[g,f,x->∞]}

If f(x)≺g(x), then f(x)≁g(x):

{f,g}={x,(x^2)};

{AsymptoticLess[f,g,x->∞],!AsymptoticEquivalent[f,g,x->∞]}

If f(x)≺g(x), then f(x)≭g(x):

{f,g}={x,(x^2)};

{AsymptoticLess[f,g,x->∞],!AsymptoticEqual[f,g,x->∞]}

If f(x)≺g(x) and g(x)⪯h(x), then f(x)≺h(x):

{f,g,h}={x,(x^2),(x^3)/(1+x)};

{AsymptoticLess[f,g,x->∞],AsymptoticLessEqual[g,h,x->∞],AsymptoticLess[f,h,x->∞]}

If f(x)≺g(x) and g(x)≍h(x), then f(x)≺h(x):

{f,g,h}={x,(x^2),(x^3)/(1+x)};

{AsymptoticLess[f,g,x->∞],AsymptoticEqual[g,h,x->∞],AsymptoticLess[f,h,x->∞]}

If f(x)≺g(x) and g(x)∼h(x), then f(x)≺h(x):

{f,g,h}={x,(x^2),(x^3)/(1+x)};

{AsymptoticLess[f,g,x->∞],AsymptoticEquivalent[g,h,x->∞],AsymptoticLess[f,h,x->∞]}

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[AsymptoticLessEqual, paclet:ref/AsymptoticLessEqual])  ▪  (RefLink[AsymptoticGreater, paclet:ref/AsymptoticGreater])  ▪  (RefLink[AsymptoticGreaterEqual, paclet:ref/AsymptoticGreaterEqual])  ▪  (RefLink[AsymptoticEqual, paclet:ref/AsymptoticEqual])  ▪  (RefLink[AsymptoticEquivalent, paclet:ref/AsymptoticEquivalent])  ▪  (RefLink[Limit, paclet:ref/Limit])  ▪  (RefLink[AsymptoticIntegrate, paclet:ref/AsymptoticIntegrate])  ▪  (RefLink[AsymptoticDSolveValue, paclet:ref/AsymptoticDSolveValue])  ▪  (RefLink[AsymptoticSum, paclet:ref/AsymptoticSum])  ▪  (RefLink[AsymptoticRSolveValue, paclet:ref/AsymptoticRSolveValue])  ▪  (RefLink[AsymptoticSolve, paclet:ref/AsymptoticSolve])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Asymptotics, paclet:guide/Asymptotics])}})}})