This site is supported by donations to The OEIS Foundation.

# Asymptotic notations

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

${\displaystyle a(n)\sim f(n):\lim _{n\to \infty }{\frac {a(n)}{f(n)}}\,=\,1.}$
${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \scriptstyle \mathrm {o} (f(n))\,}$ and big O notation originally stood for big Omicron notation ${\displaystyle \scriptstyle \mathrm {O} (f(n)).\,}$

### Little o notation

${\displaystyle o(f(n)):\lim _{n\to \infty }{\frac {a(n)}{f(n)}}\,=\,0.\,}$

#### Remark

A better although slightly more involved definition is:

${\displaystyle a\in o(f)\iff \forall \epsilon >0:|a|\leq \epsilon \cdot |f|}$ in some neighborhood of ${\displaystyle \infty }$

where the neighborhoods of infinity can be taken as sets ${\displaystyle [x_{0},\infty )}$.

Alternatively, if ${\displaystyle {\mathcal {F}}_{0}}$ denotes the functions with limit equal to zero, this can be stated as ${\displaystyle a\in o(f)\iff \exists \epsilon \in {\mathcal {F}}_{0}:|a|\leq \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

${\displaystyle O(f(n)):\exists \,c_{0},\,n_{0}~{\rm {s.t.}}~|a(n)|\,\leq \,c_{0}f(n),\,\forall n\,\geq \,n_{0}.\,}$

### θ notation

${\displaystyle \Theta (f(n)):\exists \,c_{0},\,c_{1},\,n_{0}~{\rm {s.t.}}~c_{0}f(n)\,\leq \,|a(n)|\,\leq \,c_{1}f(n),\,\forall n\,\geq \,n_{0}.\,}$
${\displaystyle \Theta (f(n))\,=\,O(f(n))\,\cap \,\Omega (f(n))\,}$.

### Big Omega notation

${\displaystyle \Omega (f(n)):\exists \,c_{0},\,n_{0}~{\rm {s.t.}}~|a(n)|\,\geq \,c_{0}f(n),\,\forall n\,\geq \,n_{0}.\,}$

### Little omega notation

${\displaystyle \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:

${\displaystyle a(n)=O(n^{3}).\,}$

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

${\displaystyle \exists f\in O(n^{3}):\ a(n)=f(n).\,}$

Similarly,

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

is interpreted as

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

## Alternate notation

The symbols ${\displaystyle \ll }$ and ${\displaystyle \gg }$ were introduced by I. M. Vinogradov.

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

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