A quick survey of asymptotic notation

Throughout this module, we are interested in leading order complexities of quantities. Consider a polynomial

\[ p(n) = 3n^3 + 5n^2 + 1. \]

If we are only interested in the asymptotic behaviour for large \(n\) then only the cubic term of \(p\) is relevant. Moreover, if we only want to express that the polynomial is growing cubically, the \(3\) in front of \(n^3\) is irrelevant. A convenient notation to express this is the \(\mathcal{O}\)-notation.

Definition of \(\mathcal{O}\)-notation

Let \(g(n)\) and \(f(n)\) be two given functions for \(n\in\mathbb{N}\). If there exists \(n_0 \in \mathbb{N}\) and a constant \(C> 0\) such that

\[ |g(n)| \leq Cf(n) \]

for all \(n\geq n_0\) we say that \(g(n) = \mathcal{O}(f(n))\).

This definition naturally extends to real variables \(x\in\mathbb{R}\) instead of integer variables \(n\).

Correspondingly, we can also use the \(\mathcal{O}\)-notation to describe how a function behaves as \(x\rightarrow 0\).

We say that \(g(x) = \mathcal{O(f(x))}\) as \(x\rightarrow 0\) if \(|g(x)| \leq Cf(x)\) for sufficiently small \(x\).

Examples

For the above polynomial, we have that

\[ p(n) = \mathcal{O}(n^3). \]

At the same time, we have that \(p(n) = \mathcal{O}(5n^3)\). However, we usually do not express constants inside the \(\mathcal{O}\)-notation unless we want to emphasise their importance, since the definition of the \(\mathcal{O}\)-notation is independent of constant factors.

For small \(x\) a typical example of the \(\mathcal{O}\)-notation is in Taylor’s theorem. For example, we have that

\[ e^{x} = 1 + x + \mathcal{O}(x^2) \]

as \(x\rightarrow 0\) as the remainder term decreases quadratically.