Mathematics.

recurrence relations

The Master Theorem

Discrete Mathematics25 minDifficulty3 out of 10

You should know: recurrence relations

Overview

The master theorem gives a direct asymptotic solution for divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n), where a ≥ 1 and b > 1 are constants and f(n) is the cost of combining subproblem results. It compares f(n) against n^(log_b a), the cost implied by the recursive branching alone, and depending on which term dominates (or whether they balance), reads off Θ(n^(log_b a)), Θ(f(n)), or a Θ(f(n) log n) hybrid. It is the standard tool for analyzing algorithms like merge sort, binary search, and Strassen's matrix multiplication without solving the recurrence by hand each time. The theorem has three standard cases, plus gaps where none apply and the Akra–Bazzi method or direct recursion-tree analysis is needed instead.

Intuition

Picture a recursion tree: at each level, work splits into a copies of size n/b, and f(n) is the extra work done at that level to stitch results together. If the tree has more total work concentrated at the leaves (many tiny subproblems dominate), the recursive branching wins — Case 1. If work is spread evenly across all log_b n levels, you get an extra log factor — Case 2. If the very first, top-level combine step already dominates everything the recursion could produce below it, that combine cost is all that matters — Case 3. The master theorem is just a shortcut for 'which level of the tree does the total work live at,' skipping the need to sum a geometric series by hand.

Formal Definition

Definition

For T(n) = aT(n/b) + f(n) with a ≥ 1, b > 1, let n^c = n^{log_b a}. Then:

Case 1: f(n)=O(nc−ϵ) for some ϵ>0  ⟹  T(n)=Θ(nc)\text{Case 1: } f(n) = O(n^{c-\epsilon}) \text{ for some } \epsilon > 0 \implies T(n) = \Theta(n^{c})
Recursion dominates
Case 2: f(n)=Θ(nc)  ⟹  T(n)=Θ(nclog⁡n)\text{Case 2: } f(n) = \Theta(n^{c}) \implies T(n) = \Theta(n^{c}\log n)
Balanced
Case 3: f(n)=Ω(nc+ϵ), af(n/b)≤kf(n) (k<1)  ⟹  T(n)=Θ(f(n))\text{Case 3: } f(n) = \Omega(n^{c+\epsilon}),\ af(n/b)\le kf(n)\ (k<1) \implies T(n) = \Theta(f(n))
Combine step dominates (regularity condition)
T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n)
General divide-and-conquer recurrence

Worked Examples

  1. Identify a=2, b=2, f(n)=n, and compute the critical exponent.

    nlog⁡ba=nlog⁡22=n1=nn^{\log_b a} = n^{\log_2 2} = n^1 = n

  2. f(n) = n = Θ(n^1), matching Case 2 exactly (balanced).

    f(n)=Θ(nc)f(n) = \Theta(n^{c})

  3. Case 2 gives an extra log factor.

    T(n)=Θ(nlog⁡n)T(n) = \Theta(n \log n)

Answer: T(n) = Θ(n log n).

Practice Problems

Difficulty 3/10

Solve T(n) = 4T(n/2) + n using the master theorem.

Difficulty 3/10

Solve T(n) = 3T(n/2) + n log n using the master theorem.

Difficulty 4/10

An algorithm makes 2 recursive calls on half-size inputs and does Θ(n²) work combining results. Determine its running time and name which master theorem case applies.

Quiz

For T(n) = aT(n/b) + f(n), the critical exponent compared against f(n) is:
Merge sort's recurrence T(n) = 2T(n/2) + n falls under which master theorem case?
If f(n) grows strictly slower than n^{log_b a} (by a polynomial factor), the master theorem concludes:

Summary

  • The master theorem solves T(n) = aT(n/b) + f(n) by comparing f(n) to the branching cost n^{log_b a}.
  • Three cases: recursion dominates (Θ(n^{log_b a})), balanced (Θ(n^{log_b a} log n)), or combine step dominates (Θ(f(n))).
  • It directly gives the running time of merge sort, binary search, and other divide-and-conquer algorithms without solving the recurrence from scratch.

References

  1. WebsiteWikipedia — Master theorem (analysis of algorithms)