Master theorem

Why this matters

Recursive algorithms take time that depends on the time of their smaller calls. Merge sort, binary search and closest pair of points all work this way. Each one can be written as a formula, called a recurrence, that says how much work a call on n items does in terms of the work on smaller inputs.

Counting the work of such an algorithm by hand, level by level, is slow and easy to get wrong. The master theorem is a rule that reads three numbers from the recurrence and gives the answer directly for a common family of recurrences. This lesson teaches how to read the three numbers and choose the case. It does not prove the theorem. Earlier lessons in this module show the halving pattern in code.

What a recurrence is

A recurrence is a formula that defines a running time in terms of the running time on smaller inputs. The usual name for the running time on an input of size n is T(n). The letter T stands for time, and n stands for the size of the input, such as the number of items in a list.

Merge sort is the standard example. To sort n items, it sorts two halves, each of size n divided by 2, and then merges the two sorted halves. The merge looks at each item once, so it costs about n steps. The total work is the work on the two halves plus the merge.

In symbols, that is T(n) = 2 T(n/2) + n. The part 2 T(n/2) says there are two calls, each on half the input. The part + n says the merge costs n steps.

The recurrence does not say the time for the smallest input. For the master theorem, that is usually written as T(1) equals a constant, such as 1. It does not change the answer, so this lesson leaves it out of the formulas.

The three numbers

Every recurrence in this lesson has the form T(n) = a T(n/b) + f(n). Three parts matter.

• a is the number of recursive calls made by one call. It is a whole number, at least 1.
• b is the factor by which the input shrinks in each recursive call. It is greater than 1. An input of size n becomes an input of size n/b.
• f(n) is the work done outside the recursive calls, at this one call. This is the splitting, merging or combining work.

Here is the merge sort recurrence again, with its three numbers marked. In T(n) = 2 T(n/2) + n, the value of a is 2, because there are two calls. The value of b is 2, because each call gets half the input. The value of f(n) is n, because the merge takes n steps.

Now a second example. Binary search looks at the middle item of a sorted list, then searches one half. It makes one call on half the input, and its work outside that call is a fixed number of steps. So a = 1, b = 2, and f(n) is a constant, which is written as 1. The recurrence is T(n) = T(n/2) + 1.

Building the answer by hand

Before using the rule, it helps to see where the answer comes from. Take T(n) = 2 T(n/2) + n and draw the calls as levels, one level per row.

Each level does the same total work, which is n. The reason is that the number of calls doubles while the size of each call halves. Doubling and halving cancel out, so the work per level stays at n.

The recursion stops when the size reaches 1. Halving n each time takes log2(n) levels. The log here is the base 2 logarithm, the number of times you can halve n before reaching 1. For n = 8 there are 3 halvings, because 8, 4, 2, 1 is three steps. For n = 1,024 there are 10. So the total work is n for each of about log2(n) levels, which is n times log2(n). This is written O(n log n).

The master theorem gets the same answer without drawing the levels. It is worth doing the drawing at least once, so that the rule does not look like magic.

The critical exponent

The rule compares f(n) with a quantity called the critical exponent, written c. It is defined as c = log base b of a. In plain words, c is the power you raise b to in order to get a. For a = 2 and b = 2, the power is 1, because 2 to the power 1 is 2. So c = 1.

The critical exponent measures how the work spreads over the levels. At the bottom of the recursion, the number of calls is a raised to the number of levels, and that equals n raised to the power c. In the example, that is n to the power 1, which is n calls at the bottom. Each of those does a constant amount of work. So the bottom level alone costs about n.

The rule then asks which part of the work is larger, the bottom or the splitting work f(n) at the top. Here f(n) is n, which matches the bottom, so the work is spread evenly over all levels.

The three cases

For this lesson, f(n) is a plain power of n, written n to the power k. So f(n) = n^k. This covers the most common recurrences. Compare k with c.

• Case 1. If k is less than c, the bottom of the recursion dominates. The answer is Θ(n^c). The symbol Θ means the running time is that growth, both above and below, up to constant factors.
• Case 2. If k equals c, the work is spread evenly over the levels. The answer is Θ(n^c log n). Here c is the critical exponent, so when c is 1 the answer is Θ(n log n).
• Case 3. If k is greater than c, the top of the recursion dominates. The answer is Θ(n^k), which is the same as f(n).

For pure powers, the extra condition needed in case 3 always holds. The condition is that the work at the top, after one split, is smaller than the work before it. With f(n) = n^k and k greater than c, the number b^k is greater than b^c, which equals a. So each level does less work than the level above it.

Read the three cases as one question: which is bigger, the number of bottom calls or the top work? The case that matches the answer is the one whose comparison holds.

Worked example 1: the case in the lesson

Take T(n) = 2 T(n/2) + n. The values are a = 2, b = 2 and f(n) = n, so k = 1.

First find c. It is log base 2 of 2, which is 1.

Then compare k with c. Both are 1. This is case 2. The answer is Θ(n^1 log n), which is Θ(n log n).

This matches the level drawing: n work on each of log2(n) levels. It also matches merge sort, which is why merge sort takes n log n time.

The program below checks the same recurrence with real numbers. It computes T(n) directly from the recurrence, for n equal to powers of 2. It also computes n times log2(n) plus n, and prints both. If the recurrence has the form the lesson describes, the two columns match.

The program prints the following on g++ 15.2.0:

a = 2, b = 2, f(n) = n^1
critical exponent log_b(a) = 1
case 2: Theta(n^1 log n)
 
        n       T(n)   n*log2(n) + n
1	1	1
16	80	80
256	2304	2304
4096	53248	53248
65536	1114112	1114112
1048576	22020096	22020096

The two columns match on every row. For powers of 2, the recurrence gives exactly n times log2(n) plus n. The n * p in the program is n times log2(n), because p is the base 2 logarithm of n when n is 2 to the power p. The extra n comes from counting level 0 as well. There are log2(n) + 1 rows in the level table, and each one does n work.

The program uses std::uint64_t, which is an unsigned 64-bit whole number. It holds values up to about 18 quintillion. Even the largest row, with n equal to about one million, is far below that limit.

Worked example 2: more calls than the split

Take T(n) = 4 T(n/2) + n. Here a = 4, b = 2 and f(n) = n, so k = 1.

The critical exponent is log base 2 of 4. That is 2, because 2 to the power 2 is 4. So c = 2.

Compare k with c. The value k is 1, which is less than 2. This is case 1, so the answer is Θ(n^2).

The level drawing shows why. Level 0 has one call of size n and does n work. Level 1 has 4 calls of size n/2, and each does n/2 work, so the level does 2n work. Level 2 has 16 calls of size n/4, each doing n/4 work, so 4n work. The work doubles from level to level, so the bottom level dominates. The bottom level has 4 raised to the power log2(n) calls, which is n^2 calls, and each does constant work.

The program below uses a small classifier. You give it a, b and k on the command line, and it prints the case and the answer. It works for any values where f(n) is a plain power of n. Save it as classify.cpp and compile it with g++ -std=c++20 -Wall -o classify classify.cpp.

The 1e-9 in the comparisons allows for rounding. Computers store decimals with limited precision, so a division can come out a hair off. The logarithm of 1000 divided by the logarithm of 10 gives 2.9999999999999996 instead of exactly 3. Without the allowance, the program could pick the wrong case for a case 2 input.

Run it on this example with ./classify 4 2 1:

T(n) = 4 T(n/2) + n^1
critical exponent = 2
case 1: Theta(n^2)

Worked example 3: the top dominates

Take T(n) = 2 T(n/2) + n^2. Here a = 2, b = 2 and f(n) = n^2, so k = 2.

The critical exponent is still 1, because a and b have not changed. Compare k with c. The value k is 2, which is greater than 1. This is case 3, so the answer is Θ(n^2).

Here is the level drawing. Level 0 does n^2 work. Level 1 has 2 calls of size n/2, each doing (n/2)^2 work, so the level does n^2/2 work. Level 2 does n^2/4. Each level is half the one above it, so the sum of all levels is at most twice the top level. The top level dominates, and the answer is n^2.

Run the classifier on it:

T(n) = 2 T(n/2) + n^2
critical exponent = 1
case 3: Theta(n^2)

This example also shows why the three cases are needed. With a = 2 and b = 2, f(n) = n gives n log n, and f(n) = n^2 gives n^2. The value of f(n) decides which level matters most.

Common mistakes

Using the wrong number for a or b

The value a counts the calls, and b counts the shrink factor. Mixing them up gives a different critical exponent. Take T(n) = T(n/2) + n. A common error is to read a as 2 because the input is halved, and to say the answer is n log n. But there is only one call, so a is 1. The critical exponent is log base 2 of 1, which is 0. Since k is 1, which is greater than 0, this is case 3, and the answer is Θ(n). The check is that the sum n + n/2 + n/4 + ... is less than 2n.

Treating f(n) as n when it is not

In T(n) = 4 T(n/2) + n^2, the value of f(n) is n squared, not n. The critical exponent is 2, and k is also 2. This is case 2, so the answer is Θ(n^2 log n), not Θ(n^2). Running the classifier catches this mistake:

T(n) = 4 T(n/2) + n^2
critical exponent = 2
case 2: Theta(n^2 log n)

The check is to write f(n) as n to some power, then compare that power with c, not with 1.

Using a rounded or truncated critical exponent

The critical exponent is usually not a whole number. A C++ program that stores it in an int gets only the whole part. The compiler warns about this if you ask for the warning. Here is a small program with a = 2 and b = 3, where the critical exponent is about 0.63:

#include <cmath>
#include <iostream>
 
int main() {
    int a = 2, b = 3;
    int crit = std::log(a) / std::log(b);
    std::cout << crit << "\n";
}

Compiling it with g++ -std=c++20 -Wall -Wconversion gives this warning:

trunc2.cpp: In function ‘int main()’:
trunc2.cpp:6:28: warning: conversion from ‘__gnu_cxx::__enable_if<true, double>::__type’ {aka ‘double’} to ‘int’ may change value [-Wfloat-conversion]
    6 |     int crit = std::log(a) / std::log(b);
      |                ~~~~~~~~~~~~^~~~~~~~~~~~~

Running it prints 0, not 0.63. The fix is to store the value in a double, as the classifier does.

Using the rule on a recurrence that is not in the form

The master theorem needs the input to shrink by a fixed factor, such as n/2. It does not apply to T(n) = T(n - 1) + n, where the input shrinks by subtracting 1. In that recurrence the work is n + (n - 1) + (n - 2) + ... + 1, which is about n^2 / 2. So the answer is Θ(n^2). The rule does not give this answer, and the classifier would give a wrong one if you tried to force the numbers in.

Writing n log n for the wrong case

Merge sort and binary search look similar in the table of cases, but they are different. Merge sort has a = 2, b = 2 and f(n) = n, which gives Θ(n log n). Binary search has a = 1, b = 2 and f(n) = 1, which gives Θ(log n). Reading the case from the numbers, not from the name of the algorithm, prevents the mistake.

Practice

Exercise 1: find the case

For the recurrence T(n) = 3 T(n/2) + n^2, find a, b, k and c. Then say which case applies and give the answer.

Show the answer

Here a = 3, b = 2 and k = 2. The critical exponent is log base 2 of 3, which is about 1.585. Since k = 2 is greater than 1.585, this is case 3. The answer is Θ(n^2). The classifier prints case 3: Theta(n^2) for this input.

Exercise 2: a fractional exponent

For T(n) = 4 T(n/3) + n, find the critical exponent and the case. Write the answer with the exponent as a logarithm, then give a decimal to two places.

Show the answer

Here a = 4, b = 3 and k = 1. The critical exponent is log base 3 of 4, which is about 1.26. Since k = 1 is less than 1.26, this is case 1. The answer is Θ(n^(log base 3 of 4)), which is about Θ(n^1.26). The classifier prints case 1: Theta(n^1.26186) for this input.

Exercise 3: a square root

For T(n) = 2 T(n/4) + sqrt(n), the work f(n) is the square root of n. Write it as n to a power, find c, and give the case and the answer.

Show the answer

The square root of n is n to the power 0.5, so k = 0.5. Here a = 2 and b = 4, so c is log base 4 of 2, which is 0.5. Since k equals c, this is case 2. The answer is Θ(sqrt(n) log n). Running ./classify 2 4 0.5 prints case 2: Theta(n^0.5 log n).

Exercise 4: binary search

Write the recurrence for binary search on n items, where each step checks the middle item and searches one half. Give a, b and f(n), then find the answer.

Show the answer

Each step makes one call on half the input and does a fixed amount of work, so T(n) = T(n/2) + 1. Here a = 1, b = 2 and f(n) = 1, which is n to the power 0. The critical exponent is 0. Since k equals c, this is case 2, and the answer is Θ(log n). Running ./classify 1 2 0 prints case 2: Theta(n^0 log n), which means Θ(log n) with the n to the power 0 left out.

Exercise 5: why the rule does not apply

Explain why the master theorem cannot give the answer for T(n) = T(n - 1) + n directly. Then give the answer by adding up the work.

Show the answer

The input shrinks by subtracting 1, not by dividing by a fixed factor b. The master theorem needs the form a T(n/b) + f(n), and this recurrence does not have that form. To get the answer by hand, add up the work at each step. The work is n at the first step, then n - 1, then n - 2, and so on down to 1. The sum is n times (n + 1) divided by 2, which is about n^2 / 2. So the answer is Θ(n^2).

Summary

• A recurrence T(n) = a T(n/b) + f(n) describes a recursive algorithm's running time.
• The three numbers are a (number of calls), b (shrink factor) and f(n) (work outside the calls).
• The critical exponent c is log base b of a, and it is compared with the power k in f(n) = n^k.
• If k is less than c, the answer is Θ(n^c). If k equals c, the answer is Θ(n^c log n). If k is greater than c, the answer is Θ(n^k).
• The rule needs the input to shrink by a fixed factor. Subtracting from the input needs a different method.