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

Formal Definition of Big-Theta

Learning the mathematical definition: f(n) = Θ(g(n)) if there exist constants c₁, c₂, n₀ such that c₁g(n) ≤ f(n) ≤ c₂g(n).

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.