It has been suggested that this article or section be merged into Big O notation. (Discuss)

In complexity theory, computer science, and mathematics, Landau notation, also called "little o"- and "big O notation", is a mathematical notation used for asymptotic comparison of functions. Wikipedia does not have an article with this exact name. ... It has been suggested that Landau notation be merged into this article or section. ... Complexity theory can refer to more than one thing: Computational complexity theory: a field in theoretical computer science and mathematics dealing with the resources required during computation to solve a given problem Systems theory (or systemics or general systems theory): an interdisciplinary field including engineering, biology and philosophy that incorporates... Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Mathematics is often defined as the study of topics such as quantity, structure, space, and change. ... It has been suggested that Landau notation be merged into this article or section. ...

More exactly, it is used to describe asymptotic upper bounds for the magnitude of a function in terms of another, usually simpler, function.

It was introduced by Paul Bachmann in the 1894 second volume of his book Analytische Zahlentheorie (the first volume, which came out in 1892, did not contain Landau notation), and popularized in the work of Edmund Landau. Paul Gustav Heinrich Bachmann (June 22, 1837 - March 31, 1920) was a German mathematician. ... Edmund Georg Hermann Landau (February 14, 1877 - February 19, 1938) was a German mathematician and author of over 250 papers on number theory. ...

Introduction

Easily understandable and detailed accounts of these notations including many examples are found in the following articles, focusing on different aspects:

• Big O notation: more explicit definitions for real valued functions, explanations, and properties of these and related notations
• Asymptotic notation: many simple examples and more on terminology, with focus on use in computational complexity
• Taylor's theorem, maybe the most important application of Landau notation in mathematical analysis,
• Asymptotic expansion: application to approximation of functions, generalizing the idea of Taylor's formula.
• Nachbin's theorem: a way of precisely bounding complex analytic functions so that the convergence of integral transforms and series transforms of the bounded function can be specified.

It has been suggested that Landau notation be merged into this article or section. ... In mathematical analysis, and in particular in the analysis of algorithms, to classify the growth of functions one has recourse to asymptotic notations. ... Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In calculus, Taylors theorem, named after the mathematician Brook Taylor, who stated it in 1712, gives the approximation of a differentiable function near a point by a polynomial whose coefficients depend only on the derivatives of the function at that point. ... Analysis is the generic name given to any branch of mathematics which depends upon the concepts of limits and convergence, and studies closely related topics such as continuity, integration, differentiability and transcendental functions. ... In mathematics an asymptotic expansion, asymptotic series or Poincaré expansion is a formal series of functions which has the property that truncating the series after a finite number of terms provides an approximation to a given function as the argument of the function tends towards a particular, often infinite, point. ... In mathematics, in the area of complex analysis, Nachbins theorem is commonly used to establish a bound on the growth rates for an analytic function. ... Complex analysis is the branch of mathematics investigating functions of complex numbers. ... In mathematics, an integral transform is any transform T of the following form: The input of this transform is a function f, and the output is another function Tf. ...

Definition

Landau's notation is defined in the following way:

If f,g are complex valued functions defined on a neighbourhood of some point x_o (which may be x=∞ on the extended real line), then In topology and related areas of mathematics, a neighbourhood (or neighborhood) is one of the basic concepts in a topological space. ... The extended real number line is obtained from the real number line R by adding two elements: +∞ and −∞ (which are not considered to be real numbers). ...

• f = O(g) (as x→x_o) iff there is C>0 such that for all x in some neighbourhood of x_o,
• f = o(g) (as x→x_o) iff for all C>0 we have for all x in some neighbourhood of x_o.

In the first case, f is called dominated by g, in the second case, f is called negligible with regard to g (in the neighbourhood of x_o). ↔ ⇔ ≡ For other possible meanings of iff, see IFF. In mathematics, philosophy, logic and technical fields that depend on them, iff is used as an abbreviation for if and only if. Common alternative phrases to iff or if and only if include Q is necessary and sufficient for P and P... ↔ ⇔ ≡ For other possible meanings of iff, see IFF. In mathematics, philosophy, logic and technical fields that depend on them, iff is used as an abbreviation for if and only if. Common alternative phrases to iff or if and only if include Q is necessary and sufficient for P and P...

Generalizations

The generalization to functions taking values in any normed vector space is straightforward (replacing absolute values by norms), where f and g need not take their values in the same space. A generalization to functions g taking values in any topological group is also possible. In mathematics, with 2- or 3-dimensional vectors with real-valued entries, the idea of the length of a vector is intuitive and can be easily extended to any real vector space Rn. ... In mathematics, a topological group G is a group that is also a topological space such that the group multiplication G × G → G and the inverse operation G → G are continuous maps. ...

The "limiting process" x→x_o can also be generalized by introducing an arbitrary filter base, i.e. to directed nets f and g. In mathematics, a filter is a special subset of a partially ordered set. ... In topology and related areas of mathematics a net or Moore-Smith sequence is a generalization of a sequence, intended to unify the various notions of limit and generalize them to arbitrary topological spaces. ...

Remarks on notation

Notice that the "=" used above does not mean equality. Use of "∈" or Hardy notation would be more logical, but is much less common. In complexity theory and mathematics, the Hardy notation, introduced by G. H. Hardy, is used for asymptotic comparison of functions, equivalently to Landau notation (aka Big O notation). It is defined in terms of Landau notation by   and   (Similar symbols are used, like TeXs preceq resp. ...

The advantage of the above notation is that it allows for the abuse of notation consisting in writing f = g + o(h) instead of f - g = o(h), which is quite handy in calculations of approximations obtained by (repeated) use of Taylor's theorem and formulae for this notation (see below). In mathematics, abuse of notation occurs when an author uses a mathematical notation in a way that is not formally correct but that seems likely to simplify the exposition while being unlikely to introduce errors or cause confusion. ... In calculus, Taylors theorem, named after the mathematician Brook Taylor, who stated it in 1712, gives the approximation of a differentiable function near a point by a polynomial whose coefficients depend only on the derivatives of the function at that point. ...

A second abuse of notation is to write f(x) (which is a number, for given x) instead of f (which is a function). This can be justified with the convention that x represents the identity function ().

Properties

Basic properties concerning this notation are the following:

• , i.e. if g = o(f), then g = O(f).

Transitivity of O and o: In grammar, a verb is transitive if it takes an object. ...

• O(O(f)) = O(f), i.e. if g = O(f) and h = O(g), then h = O(f).
• The same way, O(o(f)) = o(f) and o(O(f)) = o(f), thus also o(o(f)) = o(f).

Reflexivity of O: In mathematics, a binary relation R over a set X is reflexive if for all a in X, a is related to itself. ...

• f = O(f) (while f = o(f) implies f = o, the null function)

Thus, O is a preorder, the associated equivalence relation being asymptotic (rough) equivalence, .) This article is about the mathematics concept. ... In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ...

Stability for sum and product:

• O(f) + O(f) = O(f), i.e. if g = O(f) and h = O(f), then g + h = O(f).
• O(f) + o(f) = O(f), o(f) + o(f) = o(f).
• O(f)O(g) = O(fg), i.e. if h = O(f) and k = O(g), then hk = O(fg).
• O(f)o(g) = o(fg) and thus also o(f)o(g) = o(fg).

Note, however, that we do not have O(f) + O(g) = O(f + g), as f and g on the r.h.s. may cancel (partially). This relation is true, however, if f and g are positive (real valued) functions.

Note also that the above relations usually become wrong if they are read from right to left (in the cases where this could make sense).

Also, care should be taken to specify the point x_o whenever there could be any ambiguity on it. This is a common source of error when using Taylor's formula and changes of variables.

Applications

Main applications of Landau notations are found in complexity theory and asymptotic analysis. Complexity theory can refer to more than one thing: Computational complexity theory: a field in theoretical computer science and mathematics dealing with the resources required during computation to solve a given problem Systems theory (or systemics or general systems theory): an interdisciplinary field including engineering, biology and philosophy that incorporates... In mathematics and applications, particularly the analysis of algorithms, asymptotic analysis is a method of classifying limiting behaviour, by concentrating on some trend. ...

The o notation can be used to define derivatives and differentiability in quite general spaces, and also (asymptotical) equivalence of functions, In mathematics, the derivative is one of the two central concepts of calculus. ... In mathematics, the derivative of a function is one of the two central concepts of calculus. ...

which is a more precise notion than the rough equivalence Θ used in computational complexity theory. (It reduces to if f and g are positive real valued functions.) In computer science, computational complexity theory is the branch of the theory of computation that studies the resources, or cost, of the computation required to solve a given problem. ...