CSE 21

Math for Algorithms

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

**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-Θ.

- If the limit is

**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.