Skip to main content

Big-O and Big-Omega with curves

Short answer

Big-O: f(n) ≤ c·g(n) for n ≥ n₀, an upper bound (e.g., 5n+3 = O(n)). Big-Omega: f(n) ≥ c·g(n) for n ≥ n₀, a lower bound (e.g., 5n+3 = Ω(n)). They describe worst-case and best-case growth respectively.

Define big-O notation and Big-Omega notation with their respective curves.

Big-O notation

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 gives an asymptotic upper bound: f grows no faster than g.

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

Example: 5n + 3 ≤ 6n for n ≥ 3, so 5n + 3 = O(n).

Big-Omega notation

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

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

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

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 9 questions →