Proving Big-Theta Bounds
You'll learn how to formally prove that one function is Big-Theta of another by finding the right constants and starting point.
Big-Theta gives us a tight bound—it says two functions grow at essentially the same rate. But claiming "f(n) is Θ(g(n))" isn't enough; we need to prove it using the formal definition you just learned.
The Proof Strategy
Recall that f(n) is Θ(g(n)) if there exist positive constants c₁, c₂, and n₀ such that:
c₁ · g(n) ≤ f(n) ≤ c₂ · g(n) for all n ≥ n₀
To prove this, you need to:
- Choose your constants c₁ and c₂
- Choose your threshold n₀
- Show the inequality holds for all n beyond that threshold
Example: Prove 3n + 5 is Θ(n)
We claim f(n) = 3n + 5 is Θ(n).
Lower bound: We need c₁ · n ≤ 3n + 5
- For n ≥ 1, we know 5 ≥ 0, so 3n + 5 ≥ 3n
- Choose c₁ = 3 ✓
Upper bound: We need 3n + 5 ≤ c₂ · n
- For n ≥ 1, we have 5 ≤ 5n (true when n ≥ 1)
- So 3n + 5 ≤ 3n + 5n = 8n
- Choose c₂ = 8 ✓
Conclusion: With c₁ = 3, c₂ = 8, and n₀ = 1, we've proven 3 · n ≤ 3n + 5 ≤ 8 · n for all n ≥ 1.
Think of it like proving someone walks at roughly "your pace"—you show they're never slower than half your speed nor faster than double it, once you're both warmed up (past n₀).
Key Takeaway: To prove Big-Theta bounds, find constants that sandwich your function between two multiples of the comparison function for all sufficiently large inputs.