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

Relationship Between Big-O, Big-Omega, and Big-Theta

Understanding that Big-Theta exists when Big-O and Big-Omega have the same growth rate: Θ(g) = O(g) ∩ Ω(g).

Relationship Between Big-O, Big-Omega, and Big-Theta

What You'll Learn

You'll learn how Big-O, Big-Omega, and Big-Theta connect to give us a complete picture of an algorithm's growth rate.

The Three Notations Work Together

Think of analyzing an algorithm's runtime like describing a student's test score:

  • Big-O (O) is like saying "you scored at most 95%" — an upper bound
  • Big-Omega (Ω) is like saying "you scored at least 85%" — a lower bound
  • Big-Theta (Θ) is like saying "you scored exactly in the 90-92% range" — a tight bound

The Key Relationship

Big-Theta exists when both bounds match. Formally:

Θ(g) = O(g) ∩ Ω(g)

This means a function is Θ(g(n)) if and only if it is both O(g(n)) and Ω(g(n)).

Understanding the Intersection

When you prove an algorithm is O(n²), you've shown it won't grow faster than quadratic. When you prove it's also Ω(n²), you've shown it won't grow slower than quadratic. Together, these proofs mean the algorithm grows exactly at a quadratic rate — that's Θ(n²).

If the upper and lower bounds don't match (like O(n²) but Ω(n)), you cannot claim a Big-Theta bound. The growth rate isn't pinned down tightly enough.

Practical Meaning

Big-Theta is the strongest statement you can make. It tells you the algorithm's true growth rate. Big-O and Big-Omega alone give incomplete pictures — useful, but not the full story. When both agree, you've found the precise asymptotic behavior.

Key Takeaway: Big-Theta represents the intersection where Big-O (upper bound) and Big-Omega (lower bound) meet at the same growth rate, giving us the tightest and most accurate description of an algorithm's complexity.