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