Omega and Theta notation with example

Big Omega notation Ω (lower bound)

f(n) = Ω(g(n)) if there exist positive constants c and n₀ such that f(n) ≥ c·g(n) for all n ≥ n₀. It gives an asymptotic lower bound (best-case type guarantee).

 time
  |          f(n)
  |        .
  |      .    ___ c*g(n)
  |    .  ___/
  |  .___/
  |_/__________________ n
       n0
   f(n) >= c*g(n) for n >= n0

Example: f(n) = 3n + 2. Since 3n + 2 ≥ 3n for all n ≥ 1, f(n) = Ω(n) with c = 3, n₀ = 1.

Big Theta notation Θ (tight bound)

f(n) = Θ(g(n)) if there exist positive constants c₁, c₂ and n₀ such that c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀. The function is bounded above and below by g(n); that is, f(n) = O(g(n)) and f(n) = Ω(g(n)).

 time
  |            c2*g(n)
  |          /
  |        /  f(n)
  |      / . '
  |    / .'     c1*g(n)
  |  /.' ____--
  |_/'--________________ n
      n0

Example: f(n) = 3n + 2. For n ≥ 2: 3n ≤ 3n + 2 ≤ 4n, so c₁ = 3, c₂ = 4, n₀ = 2 and f(n) = Θ(n).

Another example: n²/2 + 3n = Θ(n²) but is not Θ(n³) (it is O(n³) only loosely).