Main Index Mathematical Analysis Inequalities
 Subject Index
comment on the page

Bachmann-Landau Asymptotic Notation

The Bachmann-Landau notation and its derivatives is used to describe the infinite or infinitesimal asymptotic behavior of functions in a neighborhood in terms of other functions.  

Let typeset structureand typeset structure an accumulation point of typeset structure.  Let typeset structure be a complex-valued function and typeset structure a positive function for all typeset structure.

The relation typeset structure as typeset structure implies that typeset structure remains bounded as typeset structure.

Examples: For typeset structure we have  typeset structure, typeset structure, typeset structure, or typeset structure, but for typeset structure we have typeset structure, typeset structure, and typeset structure.

The definitions can be extended to multiple variables in an obvious way, for instance typeset structure. Thus typeset structure for typeset structure.

Relations typeset structure, typeset structure are “one way” symbols, they cannot be read “from the right to the left”.  For instance, typeset structure and typeset structure as typeset structure, but the equality typeset structure is not true. We also have:

O (O(g(x)) = O(g(x)) br / O(o(g(x))) = o(O(g(x))) = o(o(g(x))) = o(g(x)) br / O(g(x)) &plu ... ) . O(h(x)) = O(g(x) h(x)) br / O(g(x)) . o(h(x)) = o(g(x) h(x)) br / o(g(x)) = O(g(x)), etc .

For instance, if typeset structure are continuous and typeset structure for typeset structure then typeset structure, or if typeset structure and typeset structure, then typeset structure as typeset structure.

If typeset structure and typeset structure are differentiable then typeset structure does not imply that typeset structure, but  [1] , p.297: If typeset structure and typeset structure, typeset structure, then typeset structure. If moreover, either typeset structure or  typeset structure, then typeset structure.

Remember that the implication

f(x) = O(g(x))    => h(f(x)) = O(h(g(x)))

is not true in general. For example, typeset structure but typeset structure while typeset structure. Similarly typeset structure does not imply that typeset structure.

When the involved typeset structure depends on a parameter typeset structure then we write typeset structure.

The symbols O(·) and o(·) are often attributed to E. Landau. This is only partially correct. The notation typeset structure was introduced by German number theoretist P. Bachmann [2] , p. 401,  and stood as an abbreviation for the order of and was written as a capital omicron. The notation typeset structure was introduced by E.Landau  [3], p.883  who earlier denoted this relation by {·}.

Instead of typeset structure also I.M.Vinogradov’s  “less less” notation typeset structure is used. In this case typeset structure has the same meaning as typeset structure.  [4]

There are some related symbols also in use:

If for two arbitrary functions typeset structure defined over typeset structure we have typeset structure, i.e. typeset structure which is equivalent to typeset structure then the two functions are said to be asymptotically equal, and we write typeset structure as typeset structure and typeset structure.

Recently the following notation is used in combinatorics and theoretical computer science : typeset structure, typeset structure, meaning that there is a positive constant typeset structure such that typeset structure for all sufficiently large typeset structure.

References

[1]  Jarník, V. (1956). Differential Calculus II (Czech). Prague: Publishing House of the Czechoslovak Academy of Sciences.

[2]  Bachmann, P.G.H. G. (1894). Zahlentheorie, Bd. 2: Die Analytische Zahlentheorie. Leipzig: B.G.Teubner.

[3]  Landau, E. (1909). Handbuch der Lehre von der Verteilung der Primzahlen. Leipzig: B.G.Teubner.

[4]  Knuth, D. E. (1976). Big Omicron and big Omega and big Theta. ACM SIGACT News, 8(2), 18 -24.

Cite this web-page as:

Štefan Porubský: Bachmann-Landau Asymptotic Notation.

Page created  .