Master theorem in Python

Why this matters

A recursive function calls itself on smaller inputs. A function is a named block of code, written with def in Python. Merge sort splits a list in half, sorts each half, and merges them. Binary search checks the middle and calls itself on one half. When you want to know how long such a function takes, you write a formula for its running time. That formula is called a recurrence, which means a formula that refers to itself. Solving the recurrence gives you the running time as a plain expression such as n log n.

You can solve many recurrences by drawing the calls as a tree and adding up the work on each level. The previous lesson in this module, Closest pair of points, used this kind of cost formula, and it reached O(n log n) in words, without a formula. This lesson shows the shortcut that gives that answer directly. The shortcut is the master theorem. It is a rule with three cases. You read three numbers from the recurrence, compare two of them, and the case tells you the answer.

The example in this lesson is T(n) = 2 * T(n // 2) + n. Here the function makes 2 calls, each on half the input, and does n units of work outside those calls. The master theorem says this takes O(n log n) time. You will see why, and you will use the same steps on two more worked examples.

The idea from the first principle

Start with the meaning of each symbol. T(n) is the running time for an input of size n. The letter T is just a name for "time". The size n is a count, such as the number of items in a list.

A recurrence for a divide and conquer function has three parts:

a is the number of recursive calls the function makes on each step.
b is the factor by which each call shrinks the input. A call on n / b items is a call on one bth of the input.
f(n) is the work the function does outside the recursive calls, such as splitting the input or merging the answers.

The general form is:

T(n) = a * T(n / b) + f(n)

Merge sort fits this form with a = 2, b = 2, and f(n) = n. It makes 2 calls on half the list each time, and merging the two sorted halves takes about n steps.

Drawing the calls for merge sort

Before any formula, draw what happens for a small input. Take n = 8. The first call handles 8 items and makes 2 calls on 4 items each. Each of those makes 2 calls on 2 items. Each of those makes 2 calls on 1 item. The tree has one row per level.

Here is the work per row. The level number starts at 0 for the top.

Level 0 has 1 call on 8 items. Its own work is 8.
Level 1 has 2 calls on 4 items each. Their work adds up to 8.
Level 2 has 4 calls on 2 items each. Their work adds up to 8.
Level 3 has 8 calls on 1 item each.

Every level does the same total, n, which is 8 here. The number of levels is the number of times you can halve 8 before you reach 1, which is 3. So the total is 8 times 3, which is 24.

The lesson uses a convention for the bottom: a call on 1 item costs 0 in this formula. That keeps the arithmetic exact. A real merge sort spends a small fixed amount on each one-item call, and that changes only the constant factor, not the shape of the answer.

The number 3 in that calculation is log base 2 of 8, which is the power of 2 that gives 8. Written in general, the number of levels is log n for base b, and the total is n log n.

The Python program that checks the table

The program below computes T(n) by the recurrence and compares it with n * log2(n). It also prints the level-by-level work for n = 8. It uses the math module, which is part of Python's standard library. A module is a file of code that you load with import. Save the program as master_theorem.py and run it with python3 master_theorem.py.

Python · editable

import math

def classify(a: int, b: int, d: int) -> str:
    """Classify T(n) = a * T(n / b) + n**d with the master theorem."""
    crit = math.log(a, b)
    if math.isclose(d, crit, abs_tol=1e-9):
        shape = "log n" if d == 0 else "n log n" if d == 1 else f"n^{d} log n"
        return f"critical exponent {crit:.3f}, equal to d, so case 2: Theta({shape})"
    if d < crit:
        return (f"critical exponent {crit:.3f}, d={d} is smaller, "
                f"so case 1: Theta(n^{crit:.3f})")
    ratio = a / b**d
    shape = "n" if d == 1 else f"n^{d}"
    return (f"critical exponent {crit:.3f}, d={d} is larger, "
            f"regularity ratio a/b^d = {ratio:.3f}, so case 3: Theta({shape})")

def t(n: int) -> int:
    """T(1) = 0 and T(n) = 2 * T(n // 2) + n, for powers of 2."""
    if n == 1:
        return 0
    return 2 * t(n // 2) + n

def print_levels(n: int) -> None:
    size, count, total, level = n, 1, 0, 0
    while size >= 1:
        level_work = count * (0 if size == 1 else size)
        print(f"level {level}: {count} subproblem(s) of size {size}, work {level_work}")
        total += level_work
        size //= 2
        count *= 2
        level += 1
    print("total work:", total)

if __name__ == "__main__":
    print("Example 1 (a=2, b=2, f(n)=n):", classify(2, 2, 1))
    print("Example 2 (a=1, b=2, f(n)=1):", classify(1, 2, 0))
    print("Example 3 (a=3, b=4, f(n)=n):", classify(3, 4, 1))
    print("Example 4 (a=2, b=2, f(n)=n^2):", classify(2, 2, 2))
    print("Example 5 (a=4, b=2, f(n)=n^2):", classify(4, 2, 2))
    print()

print("n, T(n), n * log2(n)")
    for k in range(11):
        n = 1 << k
        expected = 0 if k == 0 else n * k
        print(f"{n}, {t(n)}, {expected}")
    print()

print("Recursion tree for n = 8:")
    print_levels(8)

The output is:

Example 1 (a=2, b=2, f(n)=n): critical exponent 1.000, equal to d, so case 2: Theta(n log n)
Example 2 (a=1, b=2, f(n)=1): critical exponent 0.000, equal to d, so case 2: Theta(log n)
Example 3 (a=3, b=4, f(n)=n): critical exponent 0.792, d=1 is larger, regularity ratio a/b^d = 0.750, so case 3: Theta(n)
Example 4 (a=2, b=2, f(n)=n^2): critical exponent 1.000, d=2 is larger, regularity ratio a/b^d = 0.500, so case 3: Theta(n^2)
Example 5 (a=4, b=2, f(n)=n^2): critical exponent 2.000, equal to d, so case 2: Theta(n^2 log n)
 
n, T(n), n * log2(n)
1, 0, 0
2, 2, 2
4, 8, 8
8, 24, 24
16, 64, 64
32, 160, 160
64, 384, 384
128, 896, 896
256, 2048, 2048
512, 4608, 4608
1024, 10240, 10240
 
Recursion tree for n = 8:
level 0: 1 subproblem(s) of size 8, work 8
level 1: 2 subproblem(s) of size 4, work 8
level 2: 4 subproblem(s) of size 2, work 8
level 3: 8 subproblem(s) of size 1, work 0
total work: 24

The table matches n * log2(n) on every row. That is the answer the master theorem should give, and the next sections show how to get it without the table.

Three Python details appear in the program. math.log(a, b) takes the base as the second argument, so it returns log base b of a directly. n // 2 is integer division, which drops the fraction. n**d is the power operator, so n**2 is n squared.

The three cases

The master theorem compares f(n) with one special expression, n raised to the power log base b of a. Call that power c, the critical exponent. It is the number that tells you how the work splits between the levels of the tree. You can compute c by asking: what power must b be raised to get a? For a = 2 and b = 2, the answer is 1, because 2 to the power 1 is 2. So c = 1 and the special expression is n.

Then compare f(n) with n to the power c:

Case	How f(n) compares	Result
1	f(n) grows more slowly than n to the power c	Theta(n to the power c)
2	f(n) grows at the same rate	Theta(n to the power c, times log n)
3	f(n) grows faster, and f(n / b) times a is at most k times f(n) for some k below 1	Theta(f(n))

Theta is a way to say the running time grows at the same rate as the expression. It is stronger than O, which only says the running time is at most that rate.

Case 2 as written here needs f(n) to be exactly n to the power c, with no extra logarithm. A logarithm inside f(n) needs an extended form of the theorem, which this lesson does not cover. The third condition in case 3 is called the regularity check. For f(n) = n to a power d, the check reduces to one simple test that you will see in the third example.

Worked example 1: a = 2, b = 2, f(n) = n

This is the merge sort recurrence. Follow the steps in order.

Step 1: read the three numbers. The function makes a = 2 calls. Each call is on n / b, which is n / 2, so b = 2. The work outside the calls is f(n) = n.

Step 2: compute c. The power c is log base 2 of 2, which is 1. The special expression n to the power c is n to the power 1, which is n.

Step 3: compare. f(n) is n, and the special expression is also n. They are the same rate, so this is case 2.

Step 4: write the answer. Case 2 gives Theta(n to the power c, times log n). With c = 1, that is Theta(n log n).

Check it against the table. The program printed T(1024) = 10240. The number 1024 times log2(1024), which is 10, is also 10240. The formula and the tree agree.

The meaning in plain words: each of the log n levels does about n work, so the total is n times log n. The master theorem reaches the same answer without drawing the tree.

Worked example 2: a = 1, b = 2, f(n) = 1

A recursive binary search is the case where one call handles half the input and the work outside the call is constant. It checks the middle item and continues on one half. So a = 1 and b = 2, and f(n) = 1, which is the same as n to the power 0.

Step 1: read the numbers. a = 1, b = 2, and f(n) = 1.

Step 2: compute c. The power c is log base 2 of 1, which is 0, because 2 to the power 0 is 1. The special expression n to the power 0 is 1.

Step 3: compare. f(n) is 1, and the special expression is 1. They match, so this is case 2.

Step 4: write the answer. Case 2 gives Theta(n to the power 0, times log n), which is Theta(log n).

The program printed this line, which matches the reasoning:

Example 2 (a=1, b=2, f(n)=1): critical exponent 0.000, equal to d, so case 2: Theta(log n)

The meaning: the function halves the input each time, so it can halve only log n times before it reaches 1. Each halving costs a constant amount, so the total is log n.

Worked example 3: a = 3, b = 4, f(n) = n

This example has numbers that do not match the first one. Each step makes 3 calls, each on a quarter of the input, and does n work outside them.

Step 1: read the numbers. a = 3, b = 4, and f(n) = n.

Step 2: compute c. The power c is log base 4 of 3. Four to the power 0.79 is about 3, so c is about 0.792. The special expression is n to the power 0.792, which grows more slowly than n.

Step 3: compare. f(n) = n is n to the power 1. Since 1 is larger than 0.792, f(n) grows faster. That points to case 3, but case 3 also needs the regularity check.

Step 4: run the regularity check. Compute a times f(n / b). That is 3 times n / 4, which is 0.75 n. Since 0.75 n is 0.75 times f(n), and 0.75 is below 1, the check passes with k = 0.75.

Step 5: write the answer. Case 3 gives Theta(f(n)), which is Theta(n).

The program printed this line:

Example 3 (a=3, b=4, f(n)=n): critical exponent 0.792, d=1 is larger, regularity ratio a/b^d = 0.750, so case 3: Theta(n)

The meaning: the top level does n work. The next level does 0.75 n, and the level after that does 0.5625 n, and so on. The levels shrink, so the top level decides the total. The levels add up to at most n times 1 + 0.75 + 0.5625 + ..., which is 4n. So the total is Theta(n).

Common mistakes

Reading a as the exponent. In merge sort the number 2 appears in a and in b, and it is easy to write n squared by mistake. The exponent is log base b of a, which is 1, not a itself.

Skipping the comparison. The case depends on comparing f(n) with n to the power c. If you pick case 2 because the recurrence looks like merge sort, you get the wrong answer when f(n) is different. The program prints this for f(n) = n squared with a = 2 and b = 2:

Example 4 (a=2, b=2, f(n)=n^2): critical exponent 1.000, d=2 is larger, regularity ratio a/b^d = 0.500, so case 3: Theta(n^2)

The answer is n squared, not n log n. The work at the top level alone is already n squared.

Expecting the regularity check to fail. For f(n) = n to a power d, if d is bigger than c, then b to the power d is bigger than a. That makes the ratio a / b^d less than 1, so the check always passes for these functions. You only need to compute the ratio to see it.

Applying the theorem to a subtraction. The master theorem needs the input to shrink by a fixed factor b. A recurrence such as T(n) = T(n - 1) + n, where each call removes one item, is not in that form. Add the work directly instead: the work is 1 + 2 + ... + n, which is n (n + 1) / 2. That is Theta(n squared).

Swapping the arguments of math.log. The base is the second argument, so math.log(a, b) is log base b of a. Python does not complain when the order is reversed. It just returns a different number:

import math
 
print(math.log(8, 2))
print(math.log(2, 8))

The output is:

3.0
0.33333333333333337

The first line is log base 2 of 8, which is 3. The second line is log base 8 of 2, which is about one third. Both lines run without error, so a swapped argument is easy to miss.

Comparing floats with ==. A float is a number with a decimal point, and a logarithm is usually a float. Small rounding errors can make two values that should be equal differ in the last digit. Look at this program:

import math
 
print(math.log(1000, 10))
print(math.log(1000, 10) == 3)
print(math.isclose(math.log(1000, 10), 3))

The output is:

2.9999999999999996
False
True

The value is not exactly 3, so == says False. math.isclose checks that two numbers are equal up to a tiny tolerance, which is why the program uses it when it compares d with the critical exponent.

Using / where you need //. In Python, / always gives a float, even when both numbers are whole. // drops the fraction. Here is the difference:

print(5 / 2)
print(5 // 2)

The output is:

2.5
2

The recurrence splits the input into halves, so the sizes must stay whole numbers. A function that uses / gets sizes such as 2.5 and 1.25. Those never reach exactly 1, so the base case is never met. Look at this function:

def t_bad(n):
    if n == 1:
        return 0
    return 2 * t_bad(n / 2) + n
 
 
t_bad(5)

Python stops it with this error. The last lines of the output are:

    return 2 * t_bad(n / 2) + n
               ~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

A RecursionError means the function called itself more times than Python allows. By default that limit is 1000 calls. The number of repeated lines shown, and the lines above them, depend on the Python version. The fix is to write n // 2. A list with a million values needs about 20 levels of this recursion, far below the limit.

Practice

Exercise 1. Find the running time of T(n) = 4 * T(n / 2) + n. Give a, b, f(n), c, and the case.

Show the answer

a = 4, b = 2, and f(n) = n. The power c is log base 2 of 4, which is 2. The special expression is n squared, and f(n) = n grows more slowly, so this is case 1. The running time is Theta(n squared).

Exercise 2. Find the running time of T(n) = 2 * T(n / 2) + n squared.

Show the answer

a = 2, b = 2, and f(n) = n squared. The power c is 1, so the special expression is n. f(n) grows faster, so this is case 3. The regularity check is 2 * (n / 2) squared, which is n squared / 2, or half of f(n). Since 0.5 is below 1, the check passes. The running time is Theta(n squared).

Exercise 3. Find the running time of T(n) = 2 * T(n / 2) + 1. This is the recurrence for a function that splits a list in half and does one constant step.

Show the answer

a = 2, b = 2, and f(n) = 1, which is n to the power 0. The power c is 1, which is bigger than 0, so f(n) grows more slowly than the special expression. This is case 1. The running time is Theta(n). The function touches each item once in the leaves, so n is the right answer.

Exercise 4. Find the running time of T(n) = T(n / 2) + n, where the function makes one call on half the list and does n work outside it.

Show the answer

a = 1, b = 2, and f(n) = n. The power c is 0, so the special expression is 1. f(n) = n grows faster, so this is case 3. The regularity check is 1 * (n / 2), which is half of f(n), and 0.5 is below 1. The running time is Theta(n).

Exercise 5. Run classify(4, 2, 2). What does it return, and what is the answer?

Show the answer

The function returns this text:

critical exponent 2.000, equal to d, so case 2: Theta(n^2 log n)

The critical exponent is log base 2 of 4, which is 2. It equals d, so this is case 2, and the answer is Theta(n squared times log n).

Summary

A recurrence T(n) = a * T(n / b) + f(n) gives the running time of a divide and conquer function from three numbers: a calls, shrink factor b, and outside work f(n).
Compute c = log base b of a, then compare f(n) with n to the power c.
Case 1 gives Theta(n to the power c), case 2 gives Theta(n to the power c, times log n), and case 3 gives Theta(f(n)).
For merge sort, a = 2, b = 2, and f(n) = n, so the result is Theta(n log n), which the table in the program confirms.
Use // for sizes, math.log(a, b) with the base second, and math.isclose when you compare two floats.

Master theorem in Python

Why this matters

The idea from the first principle

Drawing the calls for merge sort

The Python program that checks the table

The three cases

Worked example 1: a = 2, b = 2, f(n) = n

Worked example 2: a = 1, b = 2, f(n) = 1

Worked example 3: a = 3, b = 4, f(n) = n

Common mistakes

Practice

Summary

Stuck? Ask the tutor