AsymptoticLessEqual
AsymptoticLessEqual[f,g,xx^{*}]
gives conditions for or as xx^{*}.
AsymptoticLessEqual[f,g,{x_{1},…,x_{n}}{,…,}]
gives conditions for or as {x_{1},…,x_{n}}{,…,}.
Details and Options
 Asymptotic less or equal is also expressed as f is bigo of g, f is upper bounded by g, f is of order at most g, and f grows at most as fast as g. The point x^{*} is often assumed from context.
 Asymptotic less or equal is an order relation and means when x is near x^{*} for some constant .
 Typical uses include expressing simple upper bounds for functions and sequences near some point. It is frequently used for solutions to equations and to give simple upper bounds for computational complexity.
 For a finite limit point x^{*} and {,…,}:

AsymptoticLessEqual[f[x],g[x],xx^{*}] there exist and such that implies AsymptoticLessEqual[f[x_{1},…,x_{n}],g[x_{1},…,x_{n}],{x_{1},…,x_{n}}{,…,}] there exist and such that implies  For an infinite limit point:

AsymptoticLessEqual[f[x],g[x],x∞] there exist and such that implies AsymptoticLessEqual[f[x_{1},…,x_{n}],g[x_{1},…,x_{n}],{x_{1},…,x_{n}}{∞,…,∞}] there exist and such that implies  AsymptoticLessEqual[f[x],g[x],xx^{*}] exists if and only if MaxLimit[Abs[f[x]/g[x]],xx^{*}]<∞ when g[x] does not have an infinite set of zeros near x^{*}.
 The following options can be given:

Assumptions $Assumptions assumptions on parameters Direction Reals direction to approach the limit point GenerateConditions Automatic generate conditions for parameters Method Automatic method to use PerformanceGoal "Quality" what to optimize  Possible settings for Direction include:

Reals or "TwoSided" from both real directions "FromAbove" or 1 from above or larger values "FromBelow" or +1 from below or smaller values Complexes from all complex directions Exp[ θ] in the direction {dir_{1},…,dir_{n}} use direction dir_{i} for variable x_{i} independently  DirectionExp[ θ] at x^{*} indicates the direction tangent of a curve approaching the limit point x^{*}.
 Possible settings for GenerateConditions include:

Automatic nongeneric conditions only True all conditions False no conditions None return unevaluated if conditions are needed  Possible settings for PerformanceGoal include $PerformanceGoal, "Quality" and "Speed". With the "Quality" setting, Limit typically solves more problems or produces simpler results, but it potentially uses more time and memory.
Examples
open allclose allBasic Examples (2)
Scope (9)
Compare functions that are not strictly positive:
Show that diverges no faster than at the origin:
Answers may be Boolean expressions rather than explicit True or False:
When comparing functions with parameters, conditions for the result may be generated:
By default, a twosided comparison of the functions is made:
When comparing larger values of , is indeed no bigger than :
The relationship fails for smaller values of :
Functions like Sqrt may have the same relationship in both real directions along the negative reals:
If approached from above in the complex plane, the same relationship is observed:
However, approaching from below in the complex plane produces a different result:
This is due to a branch cut where the imaginary part of Sqrt reverses sign as the axis is crossed:
Hence, the relationship does not hold in the complex plane in general:
Visualize the relative sizes of the functions when approached from the four real and imaginary directions:
Compare multivariate functions:
Visualize the norms of the two functions:
Options (10)
Assumptions (1)
Specify conditions on parameters using Assumptions:
Direction (5)
Test the relation at piecewise discontinuities:
Since it fails in one direction, the twosided result is false as well:
Visualize the two functions and their ratio:
The relationship at a simple pole is independent of the direction of approach:
Test the relation at a branch cut:
Compute the relation, approaching from different quadrants:
Approaching the origin from the first quadrant:
Approach the origin from the right halfplane:
GenerateConditions (3)
Return a result without stating conditions:
This result is only valid if n>0:
Return unevaluated if the results depend on the value of parameters:
By default, conditions are generated that guarantee a result:
By default, conditions are not generated if only special values invalidate the result:
With GenerateConditions>True, even these nongeneric conditions are reported:
PerformanceGoal (1)
Use PerformanceGoal to avoid potentially expensive computations:
The default setting uses all available techniques to try to produce a result:
Applications (10)
Basic Applications (4)
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 Log[n] steps to do the sort. Show that , so that optimal algorithms are never slower for large enough collections of objects:
Certain special algorithms (counting sort, radix sort), where there is information ahead of time about the possible inputs, can run in c n time. Show that :
Visualize the growth of the three time scales:
In a bubble sort, adjoining neighbors are compared and swapped if they are out of order. After one pass of n1 comparisons, the largest element is at the end. The process is then repeated on remaining n1 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 as follows:
Thus , and the algorithm is said to have quadratic run time:
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:
Solve the recurrence equation to find the time t to sort n elements:
Hence , and the algorithm is said to have run time:
The traveling salesperson problem (TSP) consists of finding the shortest route connecting cities. A naive algorithm is to try all routes. The Held–Karp algorithm improves that to roughly steps. Show that :
Both algorithms show that the complexity class of TSP is no worse than EXPTIME, which are problems that can be solved in time . For Held–Karp, using for some suffices:
For the factorial, it is necessary to use a higherdegree polynomial, for example :
Approximate solutions can be found in 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 :
Convergence Testing (2)
A sequence is said to be absolutely summable if . If a second sequence , the comparison test states that is absolutely summable if is. Use the test to show that converges by comparing with the sum of :
As converges, so does the sum of interest:
Compare with the answer given by SumConvergence:
Another sequence comparable to is , and thus it is also absolutely summable:
Show that convergence by comparing with the sum of :
A function is said to be absolutely integrable on if . If and are continuous on the open interval and at both and , the comparison test states that if is absolutely integrable, then is as well. Use the test to show that is absolutely integrable on :
Since and is integrable on , so is :
The function is absolutely integrable on :
At both and , , and hence the absolute integrability of follows:
Show that these functions are absolutely integrable over because is:
For , , so the comparison test gives no information about convergence:
Properties & Relations (8)
AsymptoticLessEqual is a reflexive relation, i.e. :
And it is a transitive relation, i.e. and implies :
However it is not symmetric, i.e. does not imply :
AsymptoticLessEqual[f[x],g[x],xx_{0}] iff MaxLimit[Abs[f[x]/g[x]],xx_{0}]<∞:
AsymptoticLessEqual[f[x],g[x],xx_{0}] if Limit[Abs[f[x]/g[x]],xx_{0}]<∞:
However, when the limit is Indeterminate, it is inconclusive: