Asymptotic notation lets us compare the growth rates of functions. We drop constants and small terms and keep the essence.

Three notations

  • O(g) — upper bound: f grows no faster than g.
  • Ω(g) — lower bound: f grows no slower than g.
  • Θ(g) — tight bound: f and g grow at the same rate.
f(n) between two bounds
f(n) between two bounds

The function 3n² + 5n + 7 is O(n²), Ω(n²) and therefore Θ(n²). It is also O(n³), but that is a loose bound.

The formal definition

  • f(n) = O(g(n)) if there exist c > 0 and n0 such that f(n) ≤ c · g(n) for all n ≥ n0.
  • f(n) = Ω(g(n)) if there exist c > 0 and n0 such that f(n) ≥ c · g(n) for all n ≥ n0.
  • f(n) = Θ(g(n)) if both O and Ω hold.

The sign "=" here is not equality but "belongs to the class".