This site is supported by donations to The OEIS Foundation.

# Asymptotic notations

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

$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]

## 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])