Recurrence trees

Why this matters

A recursive function calls itself on smaller inputs. To know how much work it does, you need to add up the work of every call, including the calls made by calls. For a small input you can count by hand. For n = 1000 you cannot.

A recurrence is a formula that describes the cost of a recursive function in terms of the cost of its smaller calls. Writing T(n) for the work done on an input of size n, a recurrence for a function that splits its input in two and does n units of work per call is:

T(n) = 2 T(n/2) + n

Lesson 03 in this module solved recurrences by unrolling them, replacing T with its formula over and over. This lesson uses a different picture. You draw the calls as a tree, add up the work on each level of the tree, and then count the levels. The total is the level work times the number of levels. The method gives the growth rate directly.

This lesson does not prove anything formally. It shows you how to get the answer and how to check it with a small program. The divide and conquer lessons later in the course use the same tree picture.

The idea: a tree of calls

Each call to a recursive function is a node. The calls that one call makes are its children. The first call, with the full input, is the root. A call that makes no further calls is a leaf.

Take the recurrence T(n) = 2 T(n/2) + n. The root has input size n and does n units of work. It makes two calls, each with input size n/2. Each of those makes two calls with size n/4. The tree looks like this for n = 8:

level 0:            [8]                  work 8
                  /     \
level 1:       [4]       [4]             work 4 + 4 = 8
              /   \     /   \
level 2:   [2]    [2] [2]    [2]         work 2 + 2 + 2 + 2 = 8
           / \    / \ / \    / \
level 3: [1] [1] [1][1][1][1] [1] [1]    work 0 (base case)

Each level is one row of the picture. The work on a level is the sum of the work of its nodes. Level 0 has one node of size 8, so its work is 8. Level 1 has two nodes of size 4, so its work is 8. Level 2 has four nodes of size 2, so its work is 8 again. The pattern is that the nodes on a level get smaller and more numerous, and their sizes add up to the same total.

Three facts come out of the picture:

1. Every level has the same total work, n, because the sizes on a level add up to n.
2. The sizes halve each time you go down one level, so the input reaches size 1 after about log2(n) levels. The logarithm is base 2 because the input is halved each time.
3. The total work is the work per level times the number of levels: n times log2(n).

A term needs a definition here. The logarithm of n in base 2, written log2(n), is the number of times you can halve n before you reach 1. For n = 8 that is 3, because 8 becomes 4, then 2, then 1. For n = 1024 it is 10.

The rule for a base case is also needed. A call with input size 1 does no splitting. In this lesson the base case costs 0 units of work for this recurrence, because a call on one item does no merging. The leaves therefore add nothing.

Example 1: two halves, work n per call

The recurrence T(n) = 2 T(n/2) + n describes a function that splits its input into two equal halves, does work proportional to the size of the input, and then handles both halves. Merge sort has this shape. The next program builds the tree for this function and adds the work on each level.

The helper level_totals takes three things: the starting size, a function that gives the child sizes of a node, and a function that gives the cost of a node. It walks the tree one level at a time and returns a list with the sum of the costs on each level. The lambda lines in the code are one-line functions: lambda s: s * 2 takes s and returns s * 2.

n = 8 level totals: [8, 8, 8, 0]
  levels: 4  total: 24  n * log2(n): 24
n = 16 level totals: [16, 16, 16, 16, 0]
  levels: 5  total: 64  n * log2(n): 64
n = 1024 level totals: [1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 0]
  levels: 11  total: 10240  n * log2(n): 10240

Read the output the way the tree tells you to. Every level with work totals exactly n. The last row is the level of base-case calls, which cost 0. For n = 1024 there are 10 levels with work, and 10 times 1024 is 10240, which is the total the program reports.

The tree method gives the answer before the program runs: levels times work per level is log2(n) times n. The program is only a check. It is useful because the tree can hide a mistake, such as a child size that does not add up to n. If the level totals drop when they should not, the sizes in your picture are wrong.

Now the same answer can be checked against a real function. The next program runs a real merge sort and counts how many items its merges write into their output lists. This count does not use the tree at all.

real merge sort n = 8 items written by merges = 24
real merge sort n = 16 items written by merges = 64
real merge sort n = 1024 items written by merges = 10240

The real counts match the tree totals exactly: 24, 64 and 10240. The tree predicted them without running anything.

What the total means

For the recurrence T(n) = 2 T(n/2) + n, you can write the reasoning in four lines:

1. The work per level is n.
2. The number of levels is log2(n) plus the base level.
3. The total is n times log2(n), with the base level adding nothing.
4. So the function does about n log n work.

The phrase "about" matters. When the input is not a power of 2, the sizes stop being exact halves and the count changes a little. The growth rate, n times log n, does not change. For Big-O, which is the notation for growth rate that you met in lesson 01, that is the answer you need.

Example 2: one half, work n per call

Now change the recurrence so the function makes only one call. T(n) = T(n/2) + n describes a function that does n units of work and then calls itself once on half the input.

The tree now has one node per level instead of two. Here is the picture for n = 16:

level 0:  [16]        work 16
level 1:  [8]         work 8
level 2:  [4]         work 4
level 3:  [2]         work 2
level 4:  [1]         work 0 (base case)

The level totals are 16, 8, 4, 2 and then 0. Each level is half the one before, so the total is a short series that adds up to a little less than 2n. The next program checks this for n = 16 and n = 1024.

n = 16 level totals: [16, 8, 4, 2, 0] total: 30
n = 1024 level totals: [1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 0] total: 2046

The total for n = 1024 is 2046, which is 2 times 1024 minus 2. The sum of the levels is 1024 + 512 + 256 + ... + 2. Each term is half the term before it, so the sum can never go above twice the first term. You can see this without a formal proof: the first level is n, and everything below it adds up to less than n more.

The tree method gives the growth rate in one sentence: the work per level shrinks, so the total is dominated by the first level, and the total is n times a constant. The function does linear work, which is O(n), even though it has log n levels. The levels shrink too fast to matter.

This is a useful contrast with Example 1. Two things are the same in both recurrences: the root does n units of work and the depth is log n. The difference is the number of nodes on each level. In Example 1 there are twice as many nodes each level down, so each level costs n. In Example 2 there is only one node per level, so each level costs half the one above.

Example 3: shrink by one, work n per call

Some recursive functions do not halve their input. They remove one item at a time. T(n) = T(n - 1) + n describes a function that does n units of work and then calls itself on an input one smaller. A function that adds the numbers from 1 to n by recursion has this shape.

The tree for this recurrence is a long chain. The root has size n, its only child has size n - 1, and so on down to size 1. There are n levels, not log n levels, because each step removes only one item.

level 0:  [5]      work 5
level 1:  [4]      work 4
level 2:  [3]      work 3
level 3:  [2]      work 2
level 4:  [1]      work 1

The level totals are 5, 4, 3, 2 and 1. This is the series 1 + 2 + ... + n, and it has a well known sum, n times (n + 1) divided by 2. The next program checks it for n = 5 and n = 100.

n = 5 level totals: [5, 4, 3, 2, 1, 0] total: 15
n = 100 levels: 101 total: 5050 n(n+1)/2: 5050

The total is 15 for n = 5 and 5050 for n = 100. Both match n times (n + 1) divided by 2. The growth rate is n squared, which is O(n squared). The tree shows why without the formula: there are n levels and the work on each level is at most n, so the total is at most n times n. The bound is loose by a constant factor, but the growth rate is right.

The key fact is the number of levels. When each call removes one item, the depth is n, not log n. Many beginners see a recursive function and assume the depth is logarithmic. That assumption is only correct when the input is cut by a fixed fraction at each call.

Example 4: two calls, each removing one

Now take the case where the function makes two calls, each on an input one smaller. T(n) = 2 T(n - 1) + 1 describes a function that does one unit of work and calls itself twice, each time on n - 1. The naive version of a function that computes Fibonacci numbers (each one is the sum of the two before it) by recursion has this shape.

The tree doubles at every level. The root has one node. Its two children are two nodes with size n - 1. Their four children are four nodes with size n - 2, and so on. Each node does one unit of work, so the work on level k is 2 to the power k.

The next program counts the work for n = 4 and n = 10.

n = 4 level totals: [1, 2, 4, 8, 0] total: 15
n = 10 total: 1023  2^10 - 1: 1023

The total is 2 to the power n minus 1. This is exponential growth, which is far worse than any polynomial. For n = 40 the tree has over a trillion nodes. The tree shows the cause directly: the level work doubles each time you go down, and the number of levels is n. Doubling for n levels gives 2 to the power n.

This example is a warning for function design. A recursion that makes two calls on an input that shrinks by one has exponential cost unless its results are saved and reused. The memoisation trade-offs lesson in this module (memoisation means saving each result the first time it is computed) covers how saved results change this picture. You do not need that lesson to read the tree, but you will need it to fix the cost.

Example 5: uneven split

The hardest case is a function that splits its input into two parts of different sizes. T(n) = T(n/3) + T(2n/3) + n describes a function that does n units of work and then handles one third of the input and two thirds of the input. Algorithms that split at a point that is not the middle, such as a pivot (the element the data is split around) that lands at one third of the data, have this shape.

The tree is now lopsided. The left child is one third of the size of its parent, and the right child is two thirds. Each level still adds up to at most n, because the two child sizes sum to n. The difference is the depth. The path that always takes the right child shrinks by a factor of two thirds at each step. The path that always takes the left child shrinks by a factor of one third at each step, so it ends much sooner.

Here is the tree for n = 729, which is 3 to the power 6. Each level is one row, and the number of nodes doubles at each level until the left side runs out.

level 0:  [729]                                  work 729
level 1:  [243]  [486]                           work 243 + 486 = 729
level 2:  [81] [162] [162] [324]                 work 729
level 3:  [27] [54] [54] [108] [54] [108] [108] [216]   work 729

The rows keep adding up to 729 for a while. Then the nodes from the left branch reach size 1 and cost 0, and the sums start to fall. The next program adds up the levels.

level totals: [729, 729, 729, 729, 729, 729, 728, 644, 483, 411, 171, 90, 29, 3, 2, 0]
levels: 16 total: 6935
lower bound, first 6 levels: 4374 upper bound, 16 levels times 729: 11664

The first six levels each total 729. The seventh level totals 728 because the left branch reaches size 1 at depth 6, and a size 1 call costs 0 in this model. The total is 6935.

The tree does not give the exact total here, and it does not need to. It gives two bounds that both have the form n times a count of levels:

1. Each level costs at most n, because the child sizes of a node add up to the size of the node. There are 16 levels, so the total is at most 16 times 729, which is 11664.
2. The first six levels each cost exactly 729. So the total is at least 6 times 729, which is 4374.

Both bounds are n times a logarithm. The lower one uses base 3, because six levels is the depth of the path that always takes the one third branch. The upper one uses base 1.5, because the path that always takes the two thirds branch has about log base 1.5 of n levels. Both are n log n up to a constant. So the answer is O(n log n). The exact total depends on how the sizes round, and the growth rate does not.

This is the main skill the lesson is for. You do not need the exact total. You need the level work, which is at most n, and the number of levels, which you can read from the longest path. Their product is the answer.

A method you can use on any recurrence

When you meet a recursive function, follow these steps. Write them in the margin until they become automatic.

1. Write the recurrence. Find how many child calls the function makes, what size each child gets, and how much work it does per call outside the child calls. Write it as T(n) = (calls) T(size of each child) + (work per call).
2. Draw the first three levels. Put the root at the top with size n. Under it, draw each child with its size. Stop when the pattern is clear.
3. Find the work per level. Add up the work of the nodes on each level. Check that this total is the same for every level, or find the formula that gives it for level k. In Example 1 it is n for every level. In Example 2 it halves at each level. In Example 4 the number of nodes doubles at each level.
4. Find the number of levels. Ask how many steps it takes for a size to reach the base case. Halving takes log2(n) steps. Removing one takes n steps. Cutting by a third takes log base 3 of n steps.
5. Multiply or sum. If the work per level is the same at every level, multiply it by the number of levels. If it changes, add the levels as a series. A series that shrinks fast is dominated by its first level. A series that grows fast is dominated by its last level.
6. Check with code. Build the tree in a few lines of Python, as this lesson did, and compare the level totals with your picture for a few sizes. If they disagree, your picture has a mistake in a child size or a base case.

Step 3 is where most of the thinking happens. When the work per level changes, ask which direction it moves. If it grows, the last level dominates and the total is roughly the number of leaves times the work per leaf. If it shrinks, the first level dominates and the total is roughly the root's work times a constant. If it is flat, the total is the flat work times the number of levels.

Common mistakes

Assuming every recursion has log n levels. This is the most common mistake. A recursion has log n levels only when the input shrinks by a fixed fraction at each call. When the input shrinks by one, as in Example 3, the depth is n. Look at how the child size is computed before you choose a depth.

Counting the work of the children as the work of the parent. Each level's total is the sum of the work of its own nodes. The work of a node's children belongs to the children's level. If you add the children's work into the parent's row, you count everything twice.

Forgetting the base case. A recursion with no base case, or with a base case that is never reached, does not stop. Python stops the program with a RecursionError. You can see the exact message by running this small program, which has a bug: when n is 1 it calls itself with 0, and 0 calls itself with 0 forever.

Traceback (most recent call last):
  ...
  File "...", line 4, in halve_work
    return halve_work(n // 2) + n
           ~~~~~~~~~~^^^^^^^^
  [Previous line repeated 993 more times]
RecursionError: maximum recursion depth exceeded

The traceback shows the line that repeats. The repeat count and the ^ markers can differ on another machine or Python version, but the last line is the same. The fix is a base case that returns when n is 1 or less, and no second call that runs on the same size. A correct version returns before it splits:

30

The output 30 is the total from the tree for n = 16 in Example 2. The base case is the first line of the function, so it is checked before any child call.

Mixing up the size of the children. Splitting n into halves gives children of size n/2, not n/4. Splitting into a third and two thirds gives children of size n/3 and 2n/3. If you draw the wrong size, every level total is wrong. Check that the child sizes add up to the parent size, or to at most the parent size.

Using the wrong logarithm base. Halving needs log base 2. Cutting by a third needs log base 3. The base matters for the exact count, but for Big-O the base of a logarithm does not change the growth rate, so log base 2 and log base 3 both count as O(log n). Do not spend time on the base when you are reading a growth rate. Spend it when you are predicting an exact count.

Trusting a picture you have not checked. A tree you draw by hand can have the wrong child sizes. Run the program that builds the tree for two or three inputs, as this lesson did, and compare.

Practice

Exercise 1. A function has the recurrence T(n) = 2 T(n/2) + 5, with base case T(1) = 1. It does 5 units of work per call and makes two calls on half the input. Describe the work on level k of the tree, and say whether the total is O(n) or O(n log n).

Show the answer

On level k there are 2 to the power k nodes, each with size n divided by 2 to the power k. Each node does 5 units of work, so level k costs 5 times 2 to the power k. The levels run from k = 0 to k = log2(n) minus 1, and at the bottom there are n leaves, each costing 1. The internal levels add up to 5 times (n minus 1), and the leaves add n. The total is about 6n, so the answer is O(n). The extra work of 5 per call does not change the level count, but the number of nodes doubles each level, so the total is dominated by the bottom of the tree.

Exercise 2. A function has the recurrence T(n) = T(n/4) + n. Find the number of levels, the work on each level, and the total. Check your answer with a few lines of code.

Show the answer

The size is divided by 4 at each level, so the number of levels is log4(n). The work per level is n, n/4, n/16, and so on. The sum of this series is less than n times 4 divided by 3, because each term is one quarter of the one before. So the total is O(n). A program with level_totals and the children [s // 4] gives the same shape. For n = 256, the levels are 256, 64, 16, 4, and then 0 for the base case, which total 340. That is less than 256 times 4 divided by 3, which is about 341.3.

Exercise 3. A function has the recurrence T(n) = 3 T(n/2) + n. Each call makes three child calls on half the input. Find the total work and say which level dominates.

Show the answer

Level k has 3 to the power k nodes, each of size n divided by 2 to the power k, and each node does n divided by 2 to the power k work. So the work on level k is n times (3/2) to the power k. There are log2(n) levels, and the work grows by a factor of 1.5 at each level, so the last level dominates. The last level has 3 to the power log2(n) nodes, which equals n to the power log2(3), about n to the power 1.585. The total is O(n to the power 1.585). This is more than n log n and less than n squared.

Exercise 4. Use level_totals with the children [s - 1] and the cost s to compute the total for n = 20. Then check it against the formula n times (n + 1) divided by 2.

Show the answer

The total is 210. The levels are 20, 19, 18, and so on down to 1 and then 0, and the sum of 1 to 20 is 20 times 21 divided by 2, which is 210. The program prints 210 as well, if the base case returns when the size is 0 and the cost is the size whenever the size is greater than 0.

Exercise 5. Read this function and find its complexity with a recurrence tree. Then write the recurrence.

def f(n):
    if n <= 1:
        return
    f(n // 2)
    f(n // 2)
    for i in range(n):
        pass

Show the answer

The function makes two calls on half the input and then does a loop of n passes. The recurrence is T(n) = 2 T(n/2) + n. Each level does n units of work in total, and there are log2(n) levels. The total is n times log2(n), so the function is O(n log n). The loop stands in for the merge step of merge sort, so the function has the same shape as Example 1.

Summary

• A recurrence describes the cost of a recursive function in terms of the cost of its smaller calls.
• A recursion tree draws each call as a node. The root is the first call, and the children are the calls it makes.
• Add up the work of each level. Count the levels by asking how many steps it takes for the input to reach the base case.
• The total is the level work times the number of levels, or a series of level works when they change from level to level.
• Halving the input gives log n levels. Removing one gives n levels. A tree that doubles each level with n levels gives 2 to the power n.
• Check a hand-drawn tree with a short program that builds the same tree and adds the levels.