Proving Big-Omega Bounds
What you'll learn: How to mathematically prove that a function grows at least as fast as another by finding the right constants.
The Core Idea
When you proved Big-Theta bounds in the previous lesson, you had to show both upper and lower bounds. Now we're zooming in on just the lower bound part—proving Big-Omega.
Remember that Big-Omega (Ω) describes the best-case growth rate or the minimum speed at which a function grows. To prove that f(n) is Ω(g(n)), you need to find two magic numbers:
- c (a positive constant)
- n₀ (a threshold input size)
Such that: f(n) ≥ c · g(n) for all n ≥ n₀
In plain English: "After some point n₀, my function f(n) is always at least c times bigger than g(n)."
The Proving Strategy
Step 1: Pick your target g(n) (like n, n², log n, etc.)
Step 2: Simplify f(n) by keeping only the terms that help make it bigger (drop negative terms or smaller terms)
Step 3: Find a constant c that makes the inequality work
Step 4: Determine n₀ where this becomes true for all larger n
Example
Prove f(n) = 3n² + 5n is Ω(n²):
- We need:
3n² + 5n ≥ c · n² - Since both terms are positive, we can say:
3n² + 5n ≥ 3n²(we just drop the smaller term) - Choose c = 3 and n₀ = 1
- For all n ≥ 1, our inequality holds! ✓
Key Takeaway: To prove Big-Omega bounds, find constants c and n₀ such that your function stays above c times the comparison function for all inputs beyond n₀—focus on keeping terms that make your function larger.