Order of Growth

Overview

The running time of an algorithm is usually considered as a function of its input size. How input size is measured depends on the problem at hand. For instance, sorting algorithms have an input size corresponding to the number of elements to sort.

When encountering equations with asymptotic notation on both sides of the equality, we interpret the equation using the following rule:

No matter how the anonymous functions are chosen on the left of the equal sign, there is a way to choose the anonymous functions on the right of the equal sign to make the equation valid.

For example, $2n^2+\Theta (n)=\Theta (n^2)$ states that for all $f(n)\in \Theta (n)$, there exists some $g(n)\in \Theta (n^2)$ such that $2n^2+f(n)=g(n)$.

Θ-notation

$\Theta$-notation refers to a strict lower- and upper-bound. It is defined as set $\Theta (g(n))=\{f(n)\mid \exists c_1,c_2,n_0>0,\forall n\ge n_0,0\le c_{1}g(x)\le f(n)\le c_{2}g(n)\}$

$O$-notation

$O$-notation refers to a strict upper-bound. It is defined as set $O(g(n))=\{f(n)\mid \exists c,n_0>0,\forall n\ge n_0,0\le f(n)\le cg(n)\}$

$o$-notation

$o$-notation refers to an upper bound that is not asymptotically tight. It is defined as set $o(g(n))=\{f(n)\mid \forall c>0,\exists n_0>0,\forall n\ge n_0,0\le f(n)<cg(n)\}$

Ω-notation

$\Omega$-notation refers to a strict lower-bound. It is defined as set $\Omega (g(n))=\{f(n)\mid \exists c,n_0>0,\forall n\ge n_0,0\le cg(n)\le f(n)\}$

ω-notation

$\omega$-notation refers to a lower bound that is not asymptotically tight. It is defined as set $\omega (g(n))=\{f(n)\mid \forall c>0,\exists n_0>0,\forall n\ge n_0,0\le cg(n)<f(n)\}$

Bibliography

• Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).