Big Omega

  • Express the mathematical definition of Big Omega.

Big Omega is used to describe asymptotic lower bounds!

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

Read it as

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

Ω(f(n))\Omega(f(n)) is set of functions that grow no slower than f(n)f(n).

Here is a pictorial illustration of the above definition:

If you want to prove that T(n)∈Ω(f(n))T(n) \in \Omega(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 T(n)∈Ω(n2)T(n) \in \Omega(n^2).

Solution

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

T(n)=7n2+5≥7n2 T(n) = 7n^2 + 5 \ge 7n^2

Resources