Formula & Calculator
Recurrence Relation (Master Theorem)
General form for divide-and-conquer recurrences.
Variables
| Symbol | Quantity | Unit |
|---|---|---|
| a | Number of subproblems | |
| b | Factor by which input size is divided | |
| f(n) | Cost of dividing and combining |
What it means
The master theorem is a mathematical tool for analyzing the time complexity of divide‑and‑conquer algorithms. Given a recurrence of the form T(n) = a T(n/b) + f(n), where a ≥ 1, b > 1, and f(n) is the cost of dividing and combining, the theorem provides three cases to determine the asymptotic bound. Case 1: if f(n) = O(n^(log_b a - ε)) for some ε>0, then T(n) = Θ(n^(log_b a)). Case 2: if f(n) = Θ(n^(log_b a) log^k n), then T(n) = Θ(n^(log_b a) log^(k+1) n). Case 3: if f(n) = Ω(n^(log_b a + ε)) and the regularity condition holds, then T(n) = Θ(f(n)). This theorem is essential for quickly deriving complexities of algorithms like merge sort (T(n)=2T(n/2)+n → Θ(n log n)), binary search (T(n)=T(n/2)+1 → Θ(log n)), and Strassen’s matrix multiplication. It simplifies the analysis, saving time over iterative expansion. The master theorem is a staple in algorithm analysis and is typically taught in computer science curricula.
Worked example
Master Theorem – Two Examples
Real‑World| Parameter | Value |
|---|---|
| a | 2 |
| b | 2 |
| f(n) | n |
| logba | log₂2 = 1 |
| Parameter | Value |
|---|---|
| a | 4 |
| b | 2 |
| f(n) | n |
| logba | log₂4 = 2 |
Common mistakes
- Applying to non‑divide‑and‑conquer recurrences: The master theorem only applies to recurrences of the form T(n)=aT(n/b)+f(n) with constant a≥1, b>1.
- Case selection: Identify which of the three cases applies based on f(n) relative to n^(log_b a) – mis‑classification leads to wrong Θ.
- Polynomial vs. non‑polynomial: If f(n) is not polynomially comparable, the theorem does not apply; use other methods (e.g., recursion tree).
- Base case ignored: The theorem gives asymptotic bounds; the base case affects only constants.
- Regularity condition: For case 3, check that a·f(n/b) ≤ c·f(n) for some c<1 and large n – otherwise the theorem fails.
Applications
The master theorem provides a systematic way to solve recurrence relations of the form T(n) = aT(n/b) + f(n), which arise from divide‑and‑conquer algorithms. It gives asymptotic bounds (Θ, O, Ω) for algorithms like merge sort, binary search, and matrix multiplication. This theorem is a cornerstone of algorithm analysis, enabling engineers to quickly determine the efficiency of recursive algorithms without deriving the full solution. Its applications extend to designing efficient algorithms for problems such as maximum subarray, closest pair of points, and fast Fourier transforms. In practice, understanding the master theorem helps in comparing algorithm alternatives, optimising parameters (e.g., choosing the base case size), and predicting performance on large inputs. It is an essential tool for any computer scientist or software engineer working on complex computational problems.
- Analysis of divide‑and‑conquer algorithms (merge sort, quick sort)
- Algorithm design and optimisation
- Comparison of recursive strategies
- Theoretical computer science and complexity classes
- Performance prediction for large‑scale data processing