Course contentsShow
← Computer Science
Lesson 294 of 2,8727. Introduction to Complexity AnalysisFree lesson

Proving Big-Theta Bounds

Techniques for proving a function is Big-Theta of another by finding appropriate constants and threshold values.

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:

  1. Choose your constants c₁ and c₂
  2. Choose your threshold n₀
  3. 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.