Complexity Bounds

Upper bound §

The upper bound for complexity is given as $O(f(n))$ (big-O) for some function $f$ on $n$. A function $f(n)$ can be categorised as $O(g(n))$ if there exist $c,n_0>0$ such that $0\le f(n)\le c\cdot g(n)\forall n>n_0$.

Lower bound §

The lower bound for complexity is given as $\Omega (f(n))$ (big-Omega) for some function $f$ on $n$. Similar to the Upper bound, a function $f(n)$ can be categorised as $\Omega (g(n))$ if there exist $c,n_0>0$ such that $0\le c\cdot g(n)\le f(n)\forall n\ge n_0$.

Asymptotic tight bound §

The asymptotic tight bound for complexity is given as $\Theta (f(n))$ (big-Theta) for some function $f$ on $n$. A function $f(n$) is $\Theta (g(n))$ if there exist $c_1,c_2,n_0\ge 0$ such that $0\le c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)\forall n\ge n_0$.

Tip

$f(n)$ is $\Theta (g(n))$ if and only if $f(n)$ is both $O(g(n))$ and $\Omega (g(n))$.

Strict equivalents §

Strict equivalents exist for the Upper bound and Lower bound, represented as little-o ($o(f(n))$) and little-omega ($(\omega (f(n))$) respectively. In both cases their definitions are the same as their capital equivalents, with any inequalities substituted with their strict version (ie. ’$\le$’ becomes ’$<$’).

Notation

The statement $f(n)=O(g(n))$ is written as such for brevity and is more accurately written as $f(n)\in O(g(n))$.