Master Theorem Solver (T(n) = aT(n/b) + f(n))

Understanding the master theorem solver — concept and principle

Many divide-and-conquer algorithms have running times described by a recurrence T(n) = a·T(n/b) + f(n): split a problem of size n into a subproblems of size n/b, solve them recursively, and spend f(n) work splitting and combining. The master theorem gives the asymptotic solution without unrolling the recursion. Enter a, b, the exponent k of f(n) = nᵏ and an optional log factor logᵖ n.

How it is calculated

1. Compute the critical exponent c = log_b a = ln a ÷ ln b.
2. If k < c (case 1): T(n) = Θ(n^c).
3. If k = c (case 2): T(n) = Θ(nᵏ · log^(p+1) n).
4. If k > c (case 3): T(n) = Θ(nᵏ · logᵖ n), that is Θ(f(n)).

The principle

Draw the recursion tree. Level i has aⁱ subproblems of size n/bⁱ, so the work on that level is aⁱ · f(n/bⁱ). There are about log_b n levels, and the bottom level has a^(log_b n) = n^(log_b a) leaves. The theorem simply asks which part of the tree dominates. If f grows more slowly than n^c, the leaves dominate (case 1). If f matches n^c, every level costs about the same, and multiplying by the log n levels adds one log factor (case 2). If f grows faster, the root's work dominates (case 3); for polynomial f the required regularity condition a·f(n/b) ≤ c'·f(n) with c' < 1 holds automatically.

Worked example

1. Inputs: a = 2, b = 2, k = 1, p = 0, i.e. T(n) = 2T(n/2) + n (merge sort).
2. Critical exponent: log₂ 2 = 1.
3. k = 1 equals c = 1, so case 2 applies.
4. T(n) = Θ(n¹ · log^(0+1) n) = Θ(n log n).

How to read the result

Compare the result with known algorithms: binary search (a = 1, b = 2, k = 0) gives Θ(log n); Karatsuba multiplication (a = 3, b = 2, k = 1) gives Θ(n^1.585); Strassen's matrix multiplication (a = 7, b = 2, k = 2) gives Θ(n^2.807). Reducing a, the number of subproblems, lowers the critical exponent and is often the key to a faster algorithm.

Common mistakes

• Using it when subproblems have unequal sizes, such as T(n) = T(n/3) + T(2n/3) + n; that needs the Akra–Bazzi method or a recursion tree.
• Applying it to "subtract" recurrences such as T(n) = T(n − 1) + n, which are not of the form n/b.
• Using a negative log exponent in case 2: the p + 1 rule holds only for p > −1.

Frequently asked questions

Does the base of the logarithm matter in the answer?

No. Changing the base only multiplies by a constant, so Θ(n log n) is the same class for any base.

What if f(n) is not a power of n?

The theorem still works if you can compare f with n^c polynomially; otherwise use a recursion tree or Akra–Bazzi.

Who proved the master theorem?

The general form was published by Bentley, Haken and Saxe in 1980 and popularized by the textbook of Cormen et al.

Sources: J. L. Bentley, D. Haken, J. B. Saxe, "A general method for solving divide-and-conquer recurrences", SIGACT News 12(3), 1980 · T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press (the master method) · M. Akra, L. Bazzi, "On the solution of linear recurrence equations", Computational Optimization and Applications 10, 1998