Big Oh: Mathematical Definition

T(n)∈O(f(n))⇔∃  c>0,n0>0    s.t.    T(n)≤c⋅f(n)    ∀  n≥n0 T(n) \in O(f(n))\Leftrightarrow \exists \; c > 0, n_0 > 0 \; \; s.t. \; \; T(n) \le c\cdot f(n) \; \; \forall \; n \ge n_0

Read it as

T(n)T(n) is a member of O(f(n))O(f(n)) if and only if there exist positive constants cc and n0n_0 such that T(n)≤c⋅f(n)T(n)\le c\cdot f(n) for all n≥n0n\ge n_0.

Here is a pictorial illustration of the above definition:

If you want to prove that T(n)∈O(f(n))T(n) \in O(f(n)), you need to choose the constants cc and n0n_0 so that above definition holds whenever n≥n0n \ge n_0.

Exercise The running time of an algorithm is T(n)=7n2+5T(n)=7n^2+5. Show that this algorithm has quadratic runtime, i.e. prove T(n)∈O(n2)T(n) \in O(n^2).

Solution

We can choose c=12c=12 and n0=1n_0=1 for the definition of Big Oh to hold.

There is not a systematic way to find the constants. However, you can usually play with the T(n)T(n) to find one.

T(n)=7n2+5≤7n2+5n2≤12n2 T(n) = 7n^2 + 5 \le 7n^2 + 5n^2 \le 12n^2

Resources