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

$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 $\mathrm {o} (f(n))\,$ and big O notation originally stood for big Omicron notation $\mathrm {O} (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|\leq \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|\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

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

$\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}.\,$ $\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)|\,\geq \,c_{0}f(n),\,\forall n\,\geq \,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))\,$ $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))\,$ 