The master theorem

Many recursive algorithms split their input into equal parts, solve the parts, and combine the answers. Their recurrences all have the same form, and the master theorem solves that form in one step.

The form a T(n/b) + n^d

• a is how many calls each call makes (at least 1).
• b is how many times smaller each part is (more than 1).
• n^d (d copies of n multiplied together) is the work a call does itself, outside its calls. d = 0 means a fixed amount, because n⁰ = 1, and d = 1 means work in step with n.

Merge sort is a = 2, b = 2, d = 1. Binary search is a = 1, b = 2, d = 0.

Three cases

Look at the recursion tree level by level. Level k has aᵏ calls, each of size n / bᵏ, each doing (n / bᵏ)^d work. So level k does

Every level is the level above it times the same ratio r = a / b^d. The total is a sum where each term is r times the one before. Only three things can happen:

1. r < 1, so a < b^d. Each level does less than the one above. The sum is at most a fixed multiple of its first term, so the top level decides: T(n) = Θ(n^d).
2. r = 1, so a = b^d. Every level does n^d work, and there are about log_b n levels (the number of times you can divide n by b). So T(n) = Θ(n^d log n).
3. r > 1, so a > b^d. Each level does more than the one above. The bottom level, with the most calls, decides. It has a^{log_b n} = n^{log_b a} calls, so T(n) = Θ(n^{log_b a}). Here log_b a is the power that b must be raised to, to give a: for example, log₂ 8 = 3, because 2³ = 8.

Step through the four examples and watch where the work sits:

The “sum where each term is r times the last” is called a geometric series. The fact behind case 1 is that 1 + r + r² + … stays below 1 / (1 − r) when r < 1, however many terms there are. For r = 1/2 it stays below 2.

Using it

Find a, b and d, compare a with b^d, and read off the case:

• T(n) = 2T(n/2) + n: 2 = 2¹, case 2, Θ(n log n).
• T(n) = T(n/2) + 1: 1 = 2⁰, case 2, Θ(log n).
• T(n) = 4T(n/2) + n: 4 > 2¹, case 3, Θ(n^{log₂ 4}) = Θ(n²), and n² is n times n.
• T(n) = 3T(n/2) + n: 3 > 2, case 3, Θ(n^{log₂ 3}), which is about Θ(n^1.585). This is Karatsuba’s method for multiplying large numbers (the DVCQ station).
• T(n) = 2T(n/2) + n²: 2 < 4, case 1, Θ(n²).

When it does not apply

• The parts are not equal in size, such as T(n) = T(n/3) + T(2n/3) + n. Draw the recursion tree instead.
• The input shrinks by subtracting, such as T(n) = T(n − 1) + n. That is not division by b. Unroll it as in lesson 5.
• The work outside the calls is not a power of n, such as n log n. Extended versions of the theorem exist, but a tree is simpler.

Now try BIGO-P5, Solve the recurrence, which asks you to write the theorem as a function.