Formal Definition of Big-Theta
What You'll Learn
You'll learn the precise mathematical definition that makes Big-Theta notation rigorous and unambiguous.
The Mathematical Definition
In the previous lesson, you learned that Big-Theta describes functions that grow at the same rate. Now let's make that precise.
We say f(n) = Θ(g(n)) if and only if there exist three positive constants:
- c₁ (a lower bound multiplier)
- c₂ (an upper bound multiplier)
- n₀ (a threshold input size)
Such that for all n ≥ n₀:
c₁ · g(n) ≤ f(n) ≤ c₂ · g(n)
What This Means in Plain English
Think of g(n) as a "reference function" (like n², n log n, etc.). The definition says:
"After some point (n₀), f(n) is always sandwiched between two scaled versions of g(n)."
- The function f(n) never grows faster than c₂ times g(n)
- The function f(n) never grows slower than c₁ times g(n)
- This "sandwich" only needs to hold after some starting point n₀
An Analogy
Imagine two runners on parallel tracks. If their speeds are Θ-related, one runner might start ahead or behind, but eventually they'll run at proportionally the same pace forever—one might consistently be twice as fast, but neither pulls infinitely far ahead.
Example
If f(n) = 3n² + 5n + 2, we can prove f(n) = Θ(n²) by finding:
- c₁ = 1, c₂ = 10, n₀ = 1
For all n ≥ 1: n² ≤ 3n² + 5n + 2 ≤ 10n²
Key Takeaway: Big-Theta requires proving both an upper bound (like Big-O) and a lower bound simultaneously—the function must be trapped between two constant multiples of g(n) for large inputs.