This site is supported by donations to The OEIS Foundation.

Asymptotic notations

From OeisWiki
Jump to: navigation, search


This article page is a stub, please help by expanding it.


Asymptotic notations are used to describe the limiting behavior of a function when the argument tends towards a particular value (often infinity), usually in terms of simpler functions. In computational complexity theory, big O notation is used to classify algorithms by how they respond (e.g., in their processing time or working space requirements) to changes in input size.

Asymptotic equivalence

Remarks

  • The latter may be preferable as definition because the former is ill defined when f has infinitely many zeros.
  • It is still quite customary to write "=" instead of "∈", as well in f - g = o(h) as in f = g + o(h).
  • Purists would say that the arguments (n) should not figure in the above (except in the lim(...) expression), unless one adds "as ".
  • For functions defined on IN = { 0, 1, 2, ... } the Frechet filter is tacitely understood (i.e., limit in infinity), but for functions f(x) there are ambiguities and the filter base (or limiting point) should be made precise.

Bachmann–Landau notation

Landau notation, Bachmann–Landau notation (after Edmund Landau and Paul Bachmann), or asymptotic notation.

Little o notation originally stood for little omicron notation and big O notation originally stood for big Omicron notation

Little o notation

Remark

A better although slightly more involved definition is:

in some neighborhood of

where the neighborhoods of infinity can be taken as sets .

Alternatively, if denotes the functions with limit equal to zero, this can be stated as again in some neighborhood of infinity (to take care of cases where f is zero in points where a is not).

Big O notation

θ notation

.

Big Omega notation

Little omega notation

Equality

The above notations are typically written with equality rather than set inclusion:

This should be interpreted as though quantifying over a dummy variable:

Similarly,

is interpreted as

Alternate notation

The symbols and were introduced by I. M. Vinogradov.

[1]
[2]

See also

Notes

  1. Weisstein, Eric W., Asymptotic Notation, from MathWorld—A Wolfram Web Resource. [http://mathworld.wolfram.com/AsymptoticNotation.html] ( usually stands for "precedes" or "is a predecessor of", cf. Weisstein, Eric W., Precedes, from MathWorld—A Wolfram Web Resource. [http://mathworld.wolfram.com/Precedes.html])
  2. Weisstein, Eric W., Asymptotic Notation, from MathWorld—A Wolfram Web Resource. [http://mathworld.wolfram.com/AsymptoticNotation.html] ( usually stands for "succeeds" or "is a successor of" ["succeeds" being the right verb, not "succedes"!] Cf. Weisstein, Eric W., Succeeds, from MathWorld—A Wolfram Web Resource. [http://mathworld.wolfram.com/Succeeds.html])

External links