When can I use the master theorem?

The master theorem applies to recurrences of the form T(n) = aT(n/b) + f(n) with a >= 1 and b > 1, where each level splits the problem into a subproblems of size n/b. Recurrences with uneven splits, varying subproblem sizes, or non-polynomial combine costs may need the recursion-tree, substitution, or Akra-Bazzi methods instead.

Why does mergesort's recurrence give O(n log n)?

Mergesort yields T(n) = 2T(n/2) + O(n): two half-size subproblems plus linear merging. Here the per-level work is the same across all log n levels of the recursion tree, so the total is n times log n, which the master theorem confirms as Theta(n log n).

Recurrence Relations

Recurrence relations express the running time of a recursive algorithm in terms of its running time on smaller inputs; solving them yields the closed-form asymptotic bounds used to analyze divide-and-conquer and other recursive algorithms.

Definition

A recurrence relation is an equation that defines the value of a function at an input in terms of its values at smaller inputs; in algorithm analysis, it expresses an algorithm's cost on an input of size n in terms of its cost on smaller subproblems.

Scope

This topic covers the formulation and solution of recurrences arising in algorithm analysis: the substitution method, the recursion-tree method, and the master theorem for divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n). It explains how each recursive algorithm induces a recurrence and how to translate that recurrence into a big-Theta bound. It excludes the asymptotic notation itself, which is treated separately, and combinatorial generating-function methods from discrete mathematics.

Core questions

How does a recursive algorithm give rise to a recurrence for its running time?
How is the substitution method used to prove and verify a guessed solution?
How does the recursion-tree method expose the total work across recursion levels?
When does the master theorem apply, and what do its three cases mean?
How are recurrences that fall outside the master theorem's form handled?

Key concepts

recurrence relation
substitution method
recursion-tree method
master theorem
divide-and-conquer recurrence
base case and recursive case
closed-form solution
Akra-Bazzi method

Key theories

Master theorem: For divide-and-conquer recurrences T(n) = aT(n/b) + f(n), the master theorem gives the asymptotic solution by comparing f(n) to n raised to the power log base b of a, covering the three cases where the leaves, the root, or balanced levels dominate.
Recursion-tree and substitution methods: The recursion-tree method sums the work done at each level of recursion to suggest a bound, which the substitution method then proves rigorously by induction; together they handle recurrences beyond the master theorem's scope.

Clinical relevance

Recurrence solving is the standard route to the running time of recursive algorithms, from mergesort and quicksort to fast multiplication and many dynamic programs. Engineers and researchers use the master theorem routinely to derive and justify the asymptotic complexity claims attached to such algorithms.

History

Recurrence analysis of algorithms was systematized in Knuth's The Art of Computer Programming. The master theorem became a textbook staple through CLRS, and the Akra-Bazzi method (1998) generalized it to a broader class of divide-and-conquer recurrences with uneven splits.

Key figures

Donald Knuth
Mohamad Akra
Louay Bazzi

Seminal works

cormen2009
knuth1997vol1

Frequently asked questions

When can I use the master theorem?: The master theorem applies to recurrences of the form T(n) = aT(n/b) + f(n) with a >= 1 and b > 1, where each level splits the problem into a subproblems of size n/b. Recurrences with uneven splits, varying subproblem sizes, or non-polynomial combine costs may need the recursion-tree, substitution, or Akra-Bazzi methods instead.
Why does mergesort's recurrence give O(n log n)?: Mergesort yields T(n) = 2T(n/2) + O(n): two half-size subproblems plus linear merging. Here the per-level work is the same across all log n levels of the recursion tree, so the total is n times log n, which the master theorem confirms as Theta(n log n).