Asymptotic notations

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 ℕ = {0, 1, 2, ...} the Fréchet filter is tacitly understood (i.e., limit at infinity), but for functions f(x) on the reals, 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 \mathrm {o} (f(n))\,$ and big O notation originally stood for big Omicron notation $\scriptstyle \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))\,$

See also

• Growth of sequences

External links

• Mohammad R. Salavatipour, Lecture 5: Growth of Functions, CMPUT 204: Algorithms I, Department of Computing Science, University of Alberta.