CSE 21
Math for Algorithms

Week 3 Tip

Proving Asymptotic Classes

To prove that f(n) is in Ω(g(n)), Θ(g(n)), or O(g(n)):

  1. Take the limit of f(n) / g(n) as n goes to infinity.
    • If the limit is finite, it's big-O.
    • If the limit is infinite and > 0, it's big-Ω.
    • If the limit is finite and > 0, it's big-Θ.
    You might need to L'Hôpital it a few times (differentiate top and bottom if both go to infinity). But if L'Hôpital fails you, e.g. there's a factorial involved, you should instead
  1. find witnesses C and k and prove by induction that |f(n)| ≤ C|g(n)| (if big-O) or |f(n)| ≥ C|g(n)| (if big-Ω) for all n > k. Note that if you're proving big-Θ, you need to do this both ways.

back