Skip to content

Master Theorem as Tree

Forget the Formula. Read the Tree.

The Master Theorem tells you the time complexity of recurrences like \(T(n) = aT(n/b) + f(n)\). Most textbooks give you the formula, three cases, and a table to memorize. That's backwards.

The three cases aren't arbitrary rules. They correspond to three shapes of the recursion tree. Once you draw the tree, you can read the complexity directly — no formula needed.

Building the Recursion Tree

The recurrence \(T(n) = aT(n/b) + f(n)\) says: to solve a problem of size \(n\), do \(f(n)\) work at the current level, then solve \(a\) subproblems each of size \(n/b\).

That's a tree: - Each node has \(a\) children. - The root has problem size \(n\), its children have size \(n/b\), their children have size \(n/b^2\), and so on. - The tree has depth \(\log_b n\) (because you divide by \(b\) until you reach size 1). - At depth \(d\), there are \(a^d\) nodes, each processing a problem of size \(n / b^d\).

The total work is the sum of work across all levels. And the work at level \(d\) is:

\[\text{Work at level } d = a^d \cdot f\!\left(\frac{n}{b^d}\right)\]

That's it. The "theorem" is just asking: which level dominates?

Three recursion tree shapes: leaf-heavy, balanced, and root-heavy

Case Study 1: Merge Sort — \(T(n) = 2T(n/2) + n\)

Merge sort splits the array in half (\(b = 2\)), recurses on both halves (\(a = 2\)), and merges in \(O(n)\) time (\(f(n) = n\)).

Draw the tree 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 number in brackets is the problem size at that node. The work done at each node is proportional to its problem size (the merge step).

Level Nodes Problem size Work per node Total work
0 1 8 8 8
1 2 4 4 8
2 4 2 2 8
3 8 1 0 0

Every level does exactly \(n = 8\) work. There are \(\log_2 8 = 3\) non-trivial levels.

Total work = \(n \cdot \log n = 8 \cdot 3 = 24\).

When every level does the same amount of work, the total is work-per-level times the number of levels: \(O(n \log n)\). This is the "balanced" case of the Master Theorem (Case 2: \(f(n) = \Theta(n^{\log_b a})\)).

Case Study 2: Binary Search Count — \(T(n) = 2T(n/2) + 1\)

Imagine a function that splits an array in half, recurses on both halves (\(a = 2\), \(b = 2\)), but does only \(O(1)\) work at each node (\(f(n) = 1\)).

Level 0:            [1]                   work = 1
                   /    \
Level 1:        [1]      [1]              work = 2
               /  \     /  \
Level 2:     [1]  [1] [1]  [1]            work = 4
             /\ /\  /\  /\
Level 3:   [1][1][1][1][1][1][1][1]       work = 8
Level Nodes Work per node Total work
0 1 1 1
1 2 1 2
2 4 1 4
3 8 1 8

The work doubles at each level. The last level dominates — it has more work than all other levels combined. The total is dominated by the number of leaves: \(a^{\log_b n} = 2^{\log_2 n} = n\).

When the leaves dominate, the complexity is the number of leaves: \(O(n^{\log_b a})\). This is Case 1 of the Master Theorem (\(f(n) = O(n^{\log_b a - \epsilon})\)).

Case Study 3: Root Dominates — \(T(n) = 2T(n/2) + n^2\)

Same split (\(a = 2\), \(b = 2\)), but now the work at each node is \(n^2\) — the merge is quadratic.

Level Nodes Problem size Work per node Total work
0 1 8 64 64
1 2 4 16 32
2 4 2 4 16
3 8 1 1 8

The work halves at each level. The root dominates — it does more work than all other levels combined. Total work is dominated by the root: \(O(n^2)\).

When the root dominates, the complexity is the root's work: \(O(f(n))\). This is Case 3 of the Master Theorem (\(f(n) = \Omega(n^{\log_b a + \epsilon})\)).

The Three Shapes, Side by Side

Case Tree shape Where's the work? Complexity
Leaves dominate Bottom-heavy (many small nodes) Last level \(O(n^{\log_b a})\)
All levels equal Balanced (equal work per level) Spread evenly \(O(n^{\log_b a} \log n)\)
Root dominates Top-heavy (one big node) First level \(O(f(n))\)

The deciding factor is the ratio \(a / b^c\) where \(f(n) = \Theta(n^c)\):

  • \(a > b^c\): branching outpaces shrinking → leaves dominate
  • \(a = b^c\): branching and shrinking balance → all levels equal
  • \(a < b^c\): shrinking outpaces branching → root dominates

For merge sort: \(a = 2\), \(b = 2\), \(c = 1\). \(a / b^c = 2/2 = 1\). Balanced. \(O(n \log n)\).

For the quadratic case: \(a = 2\), \(b = 2\), \(c = 2\). \(a / b^c = 2/4 = 0.5 < 1\). Root dominates. \(O(n^2)\).

Why This Matters

You don't need to memorize the Master Theorem. When you see a recurrence, draw the tree:

  1. How many children per node? (\(a\))
  2. How fast does the problem shrink? (\(b\))
  3. How much work at each node? (\(f(n)\))

Then look at the tree and ask: where's the work concentrated? Top, bottom, or spread evenly? The shape gives you the answer.

This is not a math lesson. It's a reading comprehension skill. The tree is already there in the recurrence — you just have to draw it.

Try It

The starter code runs a mock merge sort that counts total work (as the subarray length at each merge step). For \(n = 8\), predict the total work before running.

Predict before running: Each level does \(n = 8\) work, and there are \(\log_2 8 = 3\) levels. Total work = 24. But the counter also counts single-element base cases differently — trace through and verify.

Challenge: Modify the code to print work per level instead of total work. Verify that each level does exactly \(n\) work for the merge sort recurrence.

Challenge 2: What's the recursion tree for \(T(n) = 3T(n/2) + n\)? Draw it for \(n = 8\). There are \(3^3 = 27\) leaves. \(\log_2 3 \approx 1.58\), so \(n^{\log_2 3} = 8^{1.58} \approx 27\). Leaves dominate. \(O(n^{1.58})\).

Edge Cases to Watch For

  • \(n\) is not a power of \(b\): The tree levels don't divide evenly. Problem sizes at the leaves vary (some are 1, others slightly larger). The asymptotic analysis still holds, but exact counts differ.
  • \(f(n)\) has logarithmic factors: The Master Theorem's Case 2 has a variant for \(f(n) = \Theta(n^{\log_b a} \log^k n)\). The total becomes \(O(n^{\log_b a} \log^{k+1} n)\). Draw the tree to see why: each level has the same work times a log factor.
  • Non-uniform subproblem sizes: Recurrences like \(T(n) = T(n/3) + T(2n/3) + n\) don't fit the Master Theorem. Draw the tree — the longest path has depth \(\log_{3/2} n\), and each level still does \(O(n)\) work.

Problems

Problem Link Difficulty
LC 912 — Sort an Array (Merge Sort) leetcode.com/problems/sort-an-array Medium
LC 23 — Merge k Sorted Lists leetcode.com/problems/merge-k-sorted-lists Hard