asymptotic notation

In mathematical analysis, and in particular in the analysis of algorithms, to classify the growth of functions one has recourse to asymptotic notations. Knuth advocated the following notations (other notations hold in various contexts, e.g., Landau and Hardy notations):

O-notation (big-oh)
o-notation (little-oh)
Ω-notation
ω-notation
Θ-notation

The minute details of a function for arbitrary big values of its argument seldom matter. Often it is enough to compare its overall behaviour to standard sets of mathematical function so as qualify the function at hand along a restricted set of significant behaviours, such as bounded, oscillating, divergent, etc..., and to indicate the speed with which it reach this asymptotic behaviour. For instance if a function tends to zero faster than a square integrable function, it is known that it has a well-defined Fourier transform, no matter what the function actually looks like. The notation is an equality between the function at hand, and the known function it behaves like or is compared to in the asymptotic limit. For example,

g(x)=\Theta (x^2)

means that the function

g(x)

behaves asymptotically like the function

x^2

(see below for the meaning of each notation). The notation is highly conventional and must not be assigned any mathematical significance. For example, if

g=\Theta(f)

and

h=\Theta(f)

it does not mean that

g=h

. A better notation would be

g \isin \Theta (f)

\Theta(f)

(and others) can be regarded as the set of functions sharing a common asymptotic behavior.

Definitions

The O-notation means that the function is bounded from above by a function which varies like

f

, i.e.,

O(f)=\{g(x) : (\exists\alpha > 0)(\exists x_0)(\forall x>x_0)(0\le g(x)\le\alpha f(x))\}.

So that

f=O(1)

means that

f

is eventually bounded and

f=O(x)

means that

f

does not grow faster than linear (sub-linear growth). It corresponds for functions in asymptotic limit to the relation

\le

between numbers. The o-notation restricts the O-notation to mean that the function is bounded from above but that the bound is not tight, i.e., the function does not tend towards its o-reference. Formally:

o(f)=\{g(x) : (\forall\alpha>0)(\exists x_\alpha)(\forall x>x_\alpha)(0\le g(x)<\alpha f(x))\}

so that for instance

2x^n = O(x^n)

but is not

o(x^n)

. Also,

x^n = o(x^m)

n < m

while it is O if

n \le m

. It corresponds for functions in asymptotic limit to the relation > between numbers. The Ω-notation is the counterpart of O-notation for functions bounded from below:

\Omega(f)=\{g(x) : (\exists\alpha > 0)(\exists x_0)(\forall x>x_0)(0\le \alpha f(x)\ge\alpha g(x))\}.

Likewise ω-notation is the counterpart of o-notation for functions bounded from below without converging towards their reference:

\omega(f)=\{g(x) : (\forall\alpha>0)(\exists x_\alpha)(\forall x>x_\alpha)(0\le\alpha f(x)

Finally, Θ-notation means there is an asymptotically tight-bound, i.e., that the function really behaves like its reference function:

\Theta(f)=\{g(x) : (\exists\alpha>0)(\exists\beta>0)(\exists x_0)(\forall x>x_0)(0\le\alpha f(x)\le g(x)\le\beta f(x))\}.

The function can sandwiched by two representatives of its Θ-reference. For instance

x^2 + x = \Theta (x^2)

. This means that for high enough values of

x

, the function

x^2 + x

behaves like

x^2

only and its linear part has became irrelevant or negligible. It corresponds for functions in asymptotic limit to the relation

=

between numbers. In layman's terms, one would say that

$f\in O(g)$ means that f has order at most g,
$f\in \Omega(g)$ means that f has order at least g, and
$f\in \Theta(g)$ means that f has order g.

Properties

If $f\in O(g)$ and $g\in O(h)$ , then $f\in O(h)$ .
If $f\in\Theta(g)$ and $g\in\Theta(h)$ , then $f\in\Theta(h)$ .
If $f\in O(g)$ , then $g\in\Theta(f)$ .
If $f\in o(g)$ , then $f\in O(g)$ .

These notations are widely used in algorithmics to estimate the complexity of an algorithm. In mathematics it is current to use the O-notation with the meaning of the Θ-notation.

Reference

1 D. E. Knuth. Fundamental Algorithms, vol. 1 of The Art of Computer Programming.

<< Previous

Word Browser

Next >>

premier cigarette
elizabeth hurley
roll the bones
theories of new imperialism
at the drive in
relationship of command
sparta (band)
eyre coote
lumbar vertebrae
palden thondup namgyal
vote swapping

fire hydrant
charles hector, comte d'estaing
william monson
truncated cube
george pocock
1976 world surrealist exhibition
edinburgh airport
lamphun province
bmi british midland
numerical digit
lolly

lolly (disambiguation)
over governor of stockholm
program music
gary moore
romaja
ulf adelsohn
james bruce, 8th earl of elgin
mccune reischauer
mats hellstrm
gunnar heln
nils edn

thorbjrn flldin
ola ullsten
maria leissner
live from death row
royal standard
national electric drag racing association
raf mount pleasant
john ford (dramatist)
dwight gooden
john ford
john m. ford