asymptotic analysis

In mathematics and applications, particularly the analysis of algorithms, asymptotic analysis is a method of classifying limiting behaviour, by concentrating on some trend. It is sometimes expressed in the language of equivalence relations. For example, given complex-valued functions f and g of a natural number variable n, one can write

f \sim g

to express the concept that

\frac{f(n)}{g(n)} \to 1 \mbox{ as } n\to\infty

This defines an equivalence relation; and the equivalence class of f consists of all functions h with similar behaviour to f, in the limit. Asymptotic notation has been developed to provide a convenient language for the handling of statements about order of growth. It is also called Landau notation, since it became popular first in research in analytic number theory, from about 1900 onwards, introduced by Edmund Landau (originated though by Paul Bachmann). See also Big O notation, for a treatment more from the point of view of analysis of algorithms. The asymptotic point of view is basic in computer science, where the question is typically how to describe the resource implication of scaling-up the size of a computational problem, beyond the 'toy' level. An asymptotic expansion of a function f(x) is in practice an expression of that function in terms of a infinite series, the partial sums of which do not (necessarily have to) converge; but such that taking any initial partial sum provides an asymptotic formula for f. The idea is that successive terms provide a more and more accurate description of the order of growth of f. An example is Stirling's approximation. In symbols, it means we have

f \sim g_1

but also

f \sim g_1 + g_2

and

f \sim g_1 + \cdots +  g_k

for each fixed k, while some limit is taken. In the case that an asymptotic expansion does not converge, for any particular value of the argument there will be a particular partial sum which provides the best approximation and adding additional terms will decrease the accuracy. However, this optimal partial sum will generally have more terms for larger values of the argument. Asymptotic expansions typically arise in the approximation of certain integrals (saddle-point method, method of steepest descent) or in the approximation of probability distributions (Edgeworth series).

Asymptotic Analysis

Further reading