Definition:Order Notation

Definition

$\OO$-Notation

$\OO$ notation is a type of order notation, typically used in computer science for comparing 'run-times' of algorithms, or in analysis for comparing growth rates between two growth functions.

Big-$\OO$ Notation

Let $f$ and $g$ be real functions defined on a neighborhood of $+ \infty$ in $\R$.

The statement:

$\map f x = \map \OO {\map g x}$ as $x \to \infty$

is equivalent to:

$\exists c \in \R_{\ge 0}: \exists x_0 \in \R: \forall x \in \R: \paren {x \ge x_0 \implies \size {\map f x} \le c \cdot \size {\map g x} }$

That is:

$\size {\map f x} \le c \cdot \size {\map g x}$

for $x$ sufficiently large.

This statement is voiced $f$ is big-$\OO$ of $g$ or simply $f$ is big-$\OO$ $g$.

Little-$\oo$ Notation

Let $\map g x \ne 0$ for $x$ sufficiently large.

$f$ is little-$\oo$ of $g$ as $x \to \infty$ if and only if:

$\ds \lim_{x \mathop \to \infty} \frac {\map f x} {\map g x} = 0$

$\Omega$-Notation

Let $g: \N \to \R$ be a real sequence, expressed here as a real-valued function on the set of natural numbers $\N$.

Then $\map \Omega g$ is defined as:

$\map \Omega g = \set {f: \N \to \R: \exists c \in \R_{>0}: \exists n_0 \in \N: \forall n > n_0: 0 \le c \cdot \size {\map g n} \le \size {\map f n} }$

$\omega$-Notation

Let $g: \N \to \R$ be a real sequence, expressed here as a real-valued function on the set of natural numbers $\N$.

Then $\map \omega g$ is defined as:

$\map \omega g = \set {f: \N \to \R: \forall c \in \R_{>0}: \exists n_0 \in \N: \forall n > n_0: 0 \le c \cdot \size {\map g n} < \size {\map f n} }$

$\Theta$-Notation

Let $g: \N \to \R$ be a real sequence, expressed here as a real-valued function on the set of natural numbers $\N$.

Then $\map \Theta g$ is defined as:

$\map \Theta g = \map \OO g \cap \map \Omega g$

where:

$\map \OO g$ is big-$\OO$ notation

$\map \Omega g$ is big-$\Omega$ notation.

That is:

$\map \Theta g = \set {f: \N \to \R: \exists c_1, c_2 \in \R_{>0}: \exists n_0 \in \N: \forall n > n_0: 0 \le c_1 \cdot \size {\map g n} \le \size {\map f n} \le c_2 \cdot \size {\map g n} }$

Abuse of Notation

The concept of order notation is properly defined as sets of real sequences that fulfil certain properties with respect to a given real sequence.

Some sources state that extending to general real functions is an abuse of notation, although an acceptable one.

Also see

• Results about order notation can be found here.