Asymptotic Relations

Itai Seggev, Algorithms R&D, Wolfram Research
Adam Strzebonski, Algorithms R&D, Wolfram Research

Join the Conversation #WolframTechConf

ABSTRACT

One of the beautiful aspects of mathematics is that often things that look radically different are in fact the same, or at least share a common core.  On their face, algorithm analysis, function approximation and number theory seem radically different.  After all, the first is about compute programs, the second is about smooth functions, and the third is about whole numbers. However, they share a common toolset: asymptotic relations and the important concept of asymptotic scale.  By comparing the “important parts” of two functions--a common trick in mathematics--asymptotic analysis classifies functions based on the relative size of their absolute values near a particular point. Depending on the application, this comparison provides quantitative answers to questions such as “which of these algorithms is fastest” or “is function f a good approximation to function g?”.  In this talk we will survey six asymptotic relations introduced in Version 11.3 of the Wolfram Language, their applications, and their connections to the asymptotic solvers featured in a related talk.

Plan

Trace through the development of 6 asymptotic relations

({{Function, Common Notations}, {AsymptoticLess, f∈o(g), f=o(g), f≺g}, {AsymptoticLessEqual, f∈O(g), f=O(g), f⪯g}, {AsymptoticEqual, f∈Θ(g), f=Θ(g),f≍g}, {AsymptoticGreaterEqual, f∈Ω(g), f=Ω(g), f⪰g}, {AsymptoticGreater, f∈ω(g), f=ω(g), f≻g}, {AsymptoticEquivalent, f~g}})

Show some applications

Discussion connections to other parts of the larger asymptotics project

AsymptoticLessEqual (Big-O)

Popularized by Paul Bachmann in 1890’s work on analytic number theory

Appeared earlier in work Paul du Bois-Reymond

At a point (SuperStar[x]), f(x)⪯g(x) if for some constant c>0, (Abs[f(x)])≤c(Abs[g(x)]) for all x near (SuperStar[x]).

Captures the notion that f cannot become arbitrarily larger in magnitude than g

Used by Bachmann in his study of sums and the growth rate of number-theoretic functions, splitting them into explicit and ignorable terms.

Now more commonly known for application in algorithmic analysis, as popularized by Knuth

Examples

⋯⪯d(x^3)⪯c(x^2)⪯bx⪯a at 0:

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

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

a⪯bx⪯c(x^2)⪯d(x^3)⪯⋯ at ∞:

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

LogLogPlot[{1,Abs[x],Abs[10^5x],Abs[(x^2)],Abs[(x^3)]},{x,10,(10^7)},PlotLegends->"Expressions"]

(x^2)⪯ (x^2)( sin(1/x)+2)⪯x at 0:

{AsymptoticLessEqual[(x^2),(x^2)(Sin[1/x]+2),x->0],AsymptoticLessEqual[(x^2)(Sin[1/x]+2),x,x->0]}

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

AsymptoticLess (Little-O)

Introduced by Edmund Landau around 1910

Bachmann-Landau symbols in some fields/regions

At a point (SuperStar[x]), f(x)≺g(x) if for all constants c>0, (Abs[f(x)])≤c(Abs[g(x)]) for all x near (SuperStar[x]).

Quantified notion of ignorable.

Examples

⋯≺d(x^3)≺c(x^2)≺bx≺a at 0:

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

a≺bx≺c(x^2)≺d(x^3)≺⋯ at ∞:

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

Note that:

AsymptoticLess[x,(10^5)x,x->∞]

Consult the plot again:

LogLogPlot[{1,Abs[x],Abs[10^5x],Abs[(x^2)],Abs[(x^3)]},{x,10,(10^7)},PlotLegends->"Expressions"]

Similarly, (x^2)⊀ (x^2)( sin(1/x)+2)≺x at 0:

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

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

Notice one oddity of definition:

AsymptoticLess[0,0,x->a]

AsymptoticEqual (Big-Θ)

Introduced by Knuth in 1970’s

At a point (SuperStar[x]), f(x)≍g(x) if for two constants (Subscript[c, 1]),(Subscript[c, 2])>0 , (Subscript[c, 1])(Abs[g(x)])≤(Abs[f(x)])≤(Subscript[c, 2])(Abs[g(x)]) for all x near (SuperStar[x]).

Equivalently, f(x)≍g(x) iff f(x)⪯g(x)∧g(x)⪯f(x)

Examples

Two polynomials are asymptotically equal at infinity if they are of the same degree:

AsymptoticEqual[a (x^n)+b (x^k),c (x^n)+d (x^l),x->∞,Assumptions->0<k≤l<n&&a≠0&&c≠0]

Equivalently:

AsymptoticLessEqual[a (x^n)+b (x^k),c (x^n)+d (x^l),x->∞,Assumptions->0<k≤l<n&&a≠0&&c≠0]&&
AsymptoticLessEqual[c (x^n)+d (x^l),a (x^n)+b (x^k),x->∞,Assumptions->0<k≤l<n&&a≠0&&c≠0]

Visualize the ratios of three pairs of equivalent polynomials; the ratio approaches a constant (not necessarily one):

LogLogPlot[{((5(x^3)+1+50(x^2))/((x^3)+100x+75)),(((x^3)+5(x^2)+1)/((x^3)+100x+75)),((x^4)/((x^4)+100(x^2)+2500))},{x,1,1000},PlotTheme->{"Detailed","Marketing"}]

(x^2)≈(x^2) (sin(1/x)+2) at 0:

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

The ratio wiggles mercilessly, but it is bounded away from 0 and ∞:

Plot[Abs[(((x^2)(2+Sin[1/x]))/(x^2))],{x,10^-3,1/3},PlotLegends->"AllExpressions",PlotRange->{0,3}]

Applications

Analysis of algorithms

An illustration of merge sort, which is recursive splitting followed by sorted merging:

The time T[n] to sort n elements 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 (where a and b are determined by the particular computer on which the algorithm is run):

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

Solve the recurrence equation:

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

Irrespective of the particular values of a and b and the constant of summation C[1],  t ≍n log(n), and thus the algorithm is said to have n log(n) run time:

AsymptoticEqual[t,n Log[n],n->∞,Assumptions->a>0]

Any other algorithm which has n log(n) run time takes roughly the same amount of time for large inputs.  On the other hand, any algorithm with run time n, such as radix sort, will be faster for large enough inputs, because n≺n log(n):

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

Conversely, any algorithm with run time (n^2), such as bubble sort, will be slower for large inputs, as n log(n)≺(n^2):

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

Convergence testing

Two functions that are asymptotically equal to each other will have the same summation or integration convergence.  For example, (cot^(-1))(n)≍1/n  at infinity:

AsymptoticEqual[(1/n),ArcCot[n], n->∞]

It is well known that the sum of 1/n, known as the harmonic series, diverges.

DiscreteLimit[Sum[(1/n),{n,1,k}],k->∞]

Thus, (∑_(n=1)^k)(cot^(-1))(n) must also diverge.

SumConvergence[ArcCot[n], n]

OTOH, (cot^(-1))(x)/x≍1/(x^2) at both 1 and ∞:

AsymptoticEqual[((ArcCot[x])/x),(1/(x^2)), x->∞]

AsymptoticEqual[((ArcCot[x])/x),(1/(x^2)), x->1]

Thus it is integrable over [1,∞) since 1/(x^2) is:

Integrate[(1/(x^2)),{x,1,∞}]

AsymptoticGreater(Equal)—aka Little(Big)-Ω

The curse of the partial order

AsymptoticLessEqual is a partial order.  While it is the case that for any two real numbers a and b, either a≤b or b≤a, it is not true that for any two functions either f⪯g or g⪯f:

f=Sin[x];
g=1/x;
{AsymptoticLessEqual[f,g,x->∞],AsymptoticLessEqual[g,f,x->∞]}

Similarly, if a≤b, then it is true that either a==b or a<b.  But it is possible for f⪯g to be true while both f≍g and f≺g are false:

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

Note that the above means ¬(f≺g)≢g≺f:

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

Similarly ¬(f⪰g)≢g⪯f

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

Dueling conventions

Does f⪰g mean

¬(f⪰g), or

g⪯f ?

Hardy/Littlewood used the first in the 1910’s in work on elliptic functions

Knuth used the second in 1970’s in computer science

And the winner is...

Hardy/Littlewood used in analytic number theory

Knuth’s definition used in CS and related fields, as well as some others

We follow Knuth

Similarly, f≻g means g≺f.

For completeness:

At a point (SuperStar[x]), f(x)⪰g(x) if for some constant c>0, (Abs[f(x)])≥c(Abs[g(x)]) for all x near (SuperStar[x]).

At a point (SuperStar[x]), f(x)≻g(x) if for all constants c>0, (Abs[f(x)])≥c(Abs[g(x)]) for all x near (SuperStar[x]).

Again:

AsymptoticGreater[0,0,x->a]

AsymptoticEquivalent (~)

Also comes from Hardy’s work

At a point (SuperStar[x]), f(x)~g(x) if (Abs[f(x)-g(x)])≤c (Abs[g(x)])for all constants c>0  and all x near (SuperStar[x]).

Roughly: (Limit2Arg[((f(x))/(g(x))), x, (SuperStar[x])])==1

Equivalently: f-g≺f

Approximation with small relative error

Strictly finer than asymptotic equation, i.e.,

f(x)~g(x)=>f(x)≍g(x), but

f(x)≍g(x) ⇏ f(x)~g(x)

Examples

Stirling’s formula

s[n_]:=(Sqrt[2π n])(((n/E))^n)

Asymptotically equivalent to the factorial:

AsymptoticEquivalent[n!,s[n],n->∞]

Approximation with small relative, not absolute, error:

{(Underscript[\[Limit], n->∞])((n!-s[n])/(n!)),(Underscript[\[Limit], n->∞])(n!-s[n])}

Prime number theorem

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

(Underscript[\[Limit], x->∞])((PrimePi[x])/(x/Log[x]))

Again, small relative but not absolute error:

{(Underscript[\[Limit], x->∞])((PrimePi[x]-x/Log[x])/(PrimePi[x])),(Underscript[\[Limit], x->∞])(PrimePi[x]-(x/(Log[x])))}

1 is an asymptotic approximation to (e^x) at 0:

AsymptoticEquivalent[1,(E^x),x->0]

Have both small relative and absolute error:

{(Underscript[\[Limit], x->0])(((E^x)-1)/(E^x)),(Underscript[\[Limit], x->0])((E^x)-1)}

Here relative error makes no sense:

AsymptoticEquivalent[0,0,x->a]

Power Series, Asymptotic Scales, and More

Power series

Define the (k^th) Taylor (Maclaurin) polynomial to Exp[x] at 0:

taylorPolys[k_]:=Series[Exp[x],{x,0,k}]//Normal

The first five:

Table[taylorPolys[k],{k,0,4}]

By Taylor’s theorem, Taylor polynomials are asymptotic to the original function:

Table[AsymptoticEquivalent[taylorPolys[k],Exp[x],x->0],{k,0,9}]

But then so are lots of other asymptotic polynomials:

AsymptoticEquivalent[1+2x+3x^2,Exp[x],x->0]

What makes the Taylor polynomial better? The (k^th)one has small error relative to the (k^th) member of the asymptotic scale (x^n).

Table[AsymptoticLess[taylorPolys[k]-Exp[x],(x^k),x->0],{k,0,9}]

Other polynomials have small error relative to 1 only:

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

The (k^th) Taylor polynomial is the unique degree k polynomial with small error relative to (x^k).

Asymptotic scales

An asymptotic scale is a family functions for which (Subscript[f, n])≻(Subscript[f, n+1]):

AsymptoticScaleQ[list_,x_->x0_]:=And@@BlockMap[AsymptoticGreater[#1[[1]],#1[[2]],x->x0]&,list,2,1]

The power scale:

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

A Puiseux scale:

AsymptoticScaleQ[{(x^(3/2)),(x^(5/2)),(x^(7/2)),(x^(9/2)),(x^(11/2)),(x^(13/2)),(x^(15/2)),(x^(17/2))},x->0]

A couple of exponential-Puiseux scales:

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

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

Asymptotic approximation

The new asymptotic solvers automatically select appropriate scales.  Bessel’s equation:

AsymptoticDSolveValue[(-(1/4)+(x^2)) y[x]+x y'[x]+(x^2) y''[x]==0,y[x],{x,0,9}]

Airy’s equation:

AsymptoticDSolveValue[-x y[x]+y''[x]==0,y[x],{x,∞,3}]

A Laplace-type integral:

AsymptoticIntegrate[(E^(-(-2 x+(x^2)) ω)) (((1+x))^(5/2)),{x,0,∞},{ω,∞,4}]

If there exists an asymptotic approximation relative to a particular scale, it is unique

Thanks!

Our team:

Adam Strzebonski          Devendra Kapadia          Itai Seggev          Roger Germundsson

Related talks

Asymptotics Solvers

Streamlining Mathematica for Education

What’s New in Calculus and Algebra

See also http://blog.wolfram.com/2018/07/26/big-o-and-friends-tales-of-the-big-the-small-and-every-scale-in-between/

Get in touch:

itais@wolfram.com

adams@wolfram.com

Questions?