Landau notation

Encyclopedia : L : LA : LAN : Landau notation

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.

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.

Contents

1 Introduction
2 Definition

2.1 Generalizations
2.2 Remarks on notation

3 Properties
4 Applications
5 External links

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.

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

f = O(g) (as x→x_o) if and only if there is C>0 such that [|f(x)| \le C |g(x)|] for all x in some neighbourhood of x_o,
f = o(g) (as x→x_o) if and only if for all C>0 we have [|f(x)| \le C |g(x)|] 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).

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.

The "limiting process" x→x_o can also be generalized by introducing an arbitrary filter base, i.e. to directed nets f and g.

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.

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).

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 ([x\mapsto x]).

Properties

Basic properties concerning this notation are the following:

[ o(f) \subset O(f) ], i.e. if [ g=o(f) ], then [ g=O(f) ].

Transitivity of O and o:

[ 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:

[ 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, [ f = \Theta(g)\iff f=O(g)\land g=O(f) ].)

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(f g) ], i.e. if [ h=O(f) ] and [ k=O(g) ], then [ h k = O(f g) ].
[ O(f) o(g) = o(f g) ] and thus also [ o(f) o(g) = o(f g) ].

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.

The o notation can be used to define derivatives and differentiability in quite general spaces, and also (asymptotical) equivalence of functions,

[ f\sim g \iff (f-g) = o(g) ]

which is a more precise notion than the rough equivalence Θ used in computational complexity theory. (It reduces to [\lim f/g = 1] if f and g are positive real valued functions.)

External links

, [Landau Symbols] at MathWorld.

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.