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

Proving Big-Omega Bounds

Techniques for establishing lower bounds by finding constants that satisfy the Big-Omega definition.

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:

  1. c (a positive constant)
  2. 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.