Recurrence Relations and Subproblem Trees

Count work across the entire recursion tree

A recurrence models an algorithm's total work in terms of smaller inputs. For merge sort, T(n) = 2T(n/2) + Θ(n): two half-sized subproblems and linear merging work.

For eight elements, the levels have problem sizes:

Copy code8
4 + 4
2 + 2 + 2 + 2
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Each non-leaf level touches a total of eight elements, and there are logarithmically many levels. That yields Θ(n log n). By contrast, T(n) = T(n-1) + Θ(n) produces a long chain with total work n + (n-1) + ... + 1, or Θ(n²).

Time and stack depth are different: a depth-first implementation holds only one path and its unfinished work, not every node in the tree simultaneously.

Exercise

Draw the tree for T(n)=2T(n/2)+1 and calculate per-level work. Compare its Θ(n) result with merge sort.

Check: label base-case cost, branching factor, subproblem size, and work outside recursion before solving a recurrence.

Further reading: Divide-and-conquer analysis