Define Big O, Omega and Theta

Big O notation (upper bound)

f(n) = O(g(n)) if there exist positive constants c and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀. It states that f grows no faster than g (worst case guarantee).

 time
  |           c*g(n)
  |          /
  |         /  . f(n)
  |        / .
  |       /.
  |______/._____________ n
        n0

Example: 3n + 2 ≤ 4n for n ≥ 2, so 3n + 2 = O(n).

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 states that f grows at least as fast as g.

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

Example: 3n + 2 ≥ 3n for n ≥ 1, so 3n + 2 = Ω(n).

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₀. Equivalent to f = O(g) and f = Ω(g).

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

Example: 3n ≤ 3n + 2 ≤ 4n for n ≥ 2, so 3n + 2 = Θ(n).