Asymptotic notation

In computer science, asymptotic analysis is the core of complexity analysis. This is premised with the idea that we are interested in knowing how the algorithm scales with an input size that approaches infinity. There’s three main types of notation: big-O, big-omega, and big-theta notation.

$O$-notation refers to the upper bound on an algorithm’s runtime. $\Omega$-notation refers to the lower bound. $\Theta$-notation (which is like a tight upper/lower bound limit), which describes precisely how the algorithm grows. For an informal guide to finding big-O, see the page for time complexity.

Formal definition

We describe the running time of algorithms in terms of functions that maps either from/to the set of natural numbers or the set of reals. $g(n)$ represents the bound on the number of operations that an algorithm takes. $f(n)$ is the function we’re analysing, which can be more complicated than $g(n)$. The running-time function is denoted $T(n)$. If a function $f$ belongs to the set of functions (let’s use big-O), we use a notational abuse to say that $f(n)=O(g(n))$.

This figure gives some intuition on where $n_0$ comes into play.¹ Essentially the value of $f(n)$ must be on or below $cg(n)$ for values to the right of $n_0$. We’re only interested in the long-term behaviour.

Big-O

For a given function $g(n)$, we denote $O(g(n))$ as the set of functions:

$$O(g(n))=\{f(n)|\exists c,n_0>0:0\le f(n)\le cg(n)\forall n\ge n_0\}$$

i.e., $f$ belongs to $O(g(n))$ if there exists a positive constant $c$ such that $f(n)\le cg(n)$. This definition requires that any $f\in O$ is asymptotically non-negative, i.e., for sufficiently large $n$, $f$ must be non-negative.

We also define little-O $o(g(n))$, which may not be an asymptotically tight upper bound.

Big-Ω

We denote $\Omega (g(n))$ as the set of functions:

$$\Omega (g(n))=\{f(n)|\exists c,n_0>0:0\le cg(n)\le f(n)\forall n\ge n_0\}$$

i.e., an asymptotic lower bound.

We also define little-omega $\omega (g(n))$, which may not be an asymptotically tight lower bound.

Big-Θ

We denote $\Theta (g(n))$ as the set of functions:

$$\Theta (g(n))=\{f(n)|\exists c_1,c_2,n_0>0:0\le c_{1}g(n)\le f(n)\le c_{2}g(n)\forall n\ge n_0\}$$

i.e., it was an asymptotically tight bound. By theorem, we have $f(n)=\Theta (g(n))$ if and only if $f(n)=O(g(n))=\Omega (g(n))$.

Properties

• If $f(n)=\Theta (g(n))$ and $g(n)=\Theta (h(n))$, then: $f(n)=\Theta (h(n))$.
• $f(n)=\Theta (g(n))$ if and only if $g(n)=\Theta (f(n))$.
• $f(n)=O(g(n))$ if and only if $g(n)=\Omega (f(n))$.
• $n^a\le O(n^b)$ if and only if $a\le b$.
• ${\log }_{a}n=O({\log }_{b}n),\forall a,b$.
• $c^n=O(d^n)$ if and only if $c\le d$.

Then, let $f(n)=O(f^{\prime }(n))$ and $g(n)=O(g^{\prime }(n))$, where the prime denotes an arbitrary function (not the derivative), then:

• $f(n)\cdot g(n)=O(f^{\prime }(n)\cdot g^{\prime }(n))$
• $f(n)+g(n)=O(\max (f(n),g(n)))$

Footnotes

1. From CLRS’ Introduction to Algorithms. ↩