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 computer science, 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)). \,$

## 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. \,$

### 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) \lll f(n) \iff a(n) \in o(f(n)) \,$ (? TO BE CONFIRMED)
$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) \lesssim f(n) \iff a(n) \in O(f(n)) \,$
$a(n) \asymp f(n) \iff a(n) \in \Theta(f(n)) \,$
$a(n) \gtrsim f(n) \iff a(n) \in \Omega(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]
$a(n) \ggg f(n) \iff a(n) \in \omega(f(n)) \,$ (? TO BE CONFIRMED)

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