Skip to main content

DSAPath9 mincore

Master Theorem

The master theorem solves many divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n). It compares leaf work, combine work, and recursion-tree balance.

Why This Matters

Divide-and-conquer algorithms produce recurrences. The master theorem gives a fast way to classify many of them without drawing the full recursion tree every time.

Core Idea

For recurrences like:

T(n)=aT(n/b)+f(n),T(n) = aT(n/b) + f(n),

compare f(n)f(n) with nlog⁡ban^{\log_b a}, the amount of work contributed by the leaves.

Worked example: merge sort has a=2a = 2, b=2b = 2, and f(n)=nf(n) = n. Since nlog⁡22=nn^{\log_2 2} = n, the work balances across levels, so T(n)=Θ(nlog⁡n)T(n) = \Theta(n \log n).

Common Mistakes

  • Applying the theorem to recurrences that do not fit the form.
  • Forgetting regularity conditions in the larger-combine-work case.
  • Memorizing cases without understanding the recursion-tree comparison.

Exercises

  • Solve T(n)=2T(n/2)+nT(n) = 2T(n/2) + n.
  • Solve T(n)=T(n/2)+1T(n) = T(n/2) + 1.
  • Explain why uneven splits need another method.

Next Topics

References

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 4.
  • MIT OpenCourseWare. 6.046J Design and Analysis of Algorithms, Spring 2015.