Recurrence Relations and the Master Theorem
A recursive algorithm's cost is written as an equation that refers to itself, such as T(n) = 2T(n/2) + n. Solving it by expansion, by a recursion tree, or by the master theorem gives the running time without tracing a single call.
What a learner can do afterwards
- Write the recurrence for merge sort and for binary search from the code
- Expand a recurrence into a tree and sum the work level by level
- Apply the master theorem and say which of its cases a given recurrence falls in
1 · Read
Some methods call themselves on smaller inputs. You write their total cost as an equation that mentions itself. For example, T(n) = 2T(n/2) + n says the cost on size n is twice the cost on half the input, plus linear work outside the calls.
Merge sort splits the list in half, sorts both halves, then merges in linear time, so its recurrence is T(n) = 2T(n/2) + n. Binary search checks the middle once and keeps only one half, so its recurrence is T(n) = T(n/2) + 1.
To solve a recurrence, expand it into a tree. Each level of the tree is one round of calls. You add up the work level by level until the pieces reach size one.
The master theorem sorts these recurrences into three cases. In the first case the leaves dominate, in the second every level ties, and in the third the work outside the calls dominates. Name the case by comparing the leaf work with the outside work.
Write the cost as an equation about itself, expand it level by level, then name the master theorem case.
2 · Watch
Take it off screen
Where it sits
Learn first
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.