Solve a Recurrence With a Recursion Tree

A recursion tree solves a recurrence by drawing every call as a node, labelling each node with the work that call does outside its own recursive calls, and adding the work one level at a time. This card solves T(n) = 2T(n/2) + n, the recurrence of merge sort, first for n = 8 and then for any n.

The method has four moves: draw the root with its work f(n); give each node its a children, each of size n/b; stop at the base case; then total each level and add the totals. Here a node of size m does m work, and a node of size 1 does 1.

The tree below is merge sort's on 7 3 9 1 6 8 2 5, each node named by the part of the array that call sorts, with the work it does in its own merge.

Read the tree across rather than down. Each level has twice as many nodes as the one above, and each node is half the size, so the two effects cancel. A program that expanded every call and totalled the levels printed the same figures as the table.

Every level costs 8, there are four levels, and the total is 32. For any n that is a power of two the same pattern holds. Level k has 2ᵏ nodes of size n/2ᵏ, so every level costs n. The sizes halve from n down to 1, which takes log₂ n halvings, so there are log₂ n + 1 levels counting the root. The total is n(log₂ n + 1), and at n = 8 that is 8 × 4 = 32. Dropping the smaller term gives O(n log n), merge sort's running time on every input.

The slip to avoid is counting the halvings, log₂ n, as the levels. The root is a level too, and leaving it out loses one level's work, n of the 32 here.

The level totals do not always come out equal, and their pattern decides the answer. When they are equal, the cost is one level's work times the number of levels. When they grow on the way down, the leaves outweigh everything above them, and when they shrink, the root does. The master theorem names those three patterns and gives the answer for each without drawing the tree.