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.

Contents

Asymptotic equivalence

a(n) \sim f(n): \lim_{n \to \infty} \frac{a(n)}{f(n)} \,=\, 1.
a(n) \sim f(n) \iff (a(n) - f(n)) \in o(f(n)).

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 n\to\infty".
  • 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 \scriptstyle \omicron(f(n)) \, and big O notation originally stood for big Omicron notation \scriptstyle \Omicron(f(n)). \,

Little o notation

o(f(n)): \lim_{n \to \infty} \frac{a(n)}{f(n)} \,=\, 0. \,

Remark

A better although slightly more involved definition is:

a \in o(f) \iff \forall\epsilon>0: |a| \le \epsilon\cdot|f| in some neighborhood of \infty

where the neighborhoods of infinity can be taken as sets [x_0,\infty).

Alternatively, if \mathcal F_0 denotes the functions with limit equal to zero, this can be stated as a \in o(f) \iff \exists\epsilon\in\mathcal F_0: |a| \le \epsilon\cdot|f|, again in some neighborhood of infinity (to take care of cases where f is zero in points where a is not).

Big O notation

O(f(n)): \exists \, c_0,\, n_0 ~{\rm s.t.}~ |a(n)| \,\le\, c_0 f(n),\, \forall n \,\ge\, n_0. \,

θ notation

\Theta(f(n)): \exists \, c_0,\, c_1,\, n_0 ~{\rm s.t.}~ c_0 f(n) \,\le\, |a(n)| \,\le\, c_1 f(n),\, \forall n \,\ge\, n_0. \,
\Theta(f(n)) \,=\, O(f(n)) \,\cap\, \Omega(f(n)) \,.

Big Omega notation

\Omega(f(n)): \exists \, c_0,\, n_0 ~{\rm s.t.}~ |a(n)| \,\ge\, c_0 f(n),\, \forall n \,\ge\, n_0. \,

Little omega notation

\omega(f(n)): \lim_{n \to \infty} \frac{a(n)}{f(n)} \,=\, \infty. \,

Equality

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

a(n) = O(n^3). \,

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

\exists f \in O(n^3):\ a(n) = f(n). \,

Similarly,

a(n) = 2^{n+o(1)} \,

is interpreted as

\exists f \in o(1):\ a(n) = 2^{n+f(n)}. \,

Alternate notation

The symbols \ll and \gg were introduced by I. M. Vinogradov.

a(n) \prec f(n) \iff a(n) \in o(f(n)) \, [1]
a(n) \ll f(n) \iff a(n) \in O(f(n)) \,
a(n) \asymp f(n) \iff a(n) \in \Theta(f(n)) \,
a(n) \gg f(n) \iff a(n) \in \Omega(f(n)) \,
a(n) \succ f(n) \iff a(n) \in \omega(f(n)) \, [2]

See also

Notes

  1. Weisstein, Eric W., Asymptotic Notation, from MathWorld—A Wolfram Web Resource. [http://mathworld.wolfram.com/AsymptoticNotation.html] (\prec \, 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] (\succ \, 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

Personal tools