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.
More to read
Simple math recursion
Recursion is when a function calls itself to solve a smaller version of the same problem. Every recursive function needs two parts. First, the base case: the small problem you can answer directly, like 1! = 1. Second, the recursive case: the rule that shrinks the problem, like n! = n times (n-1)!. To compute 5!, the function asks for 4!, which asks for 3!, and so on until the base case hands back 1. Then the answers multiply back up the chain: 2 times 1 is 2, 3 times 2 is 6, 4 times 6 is 24, 5 times 24 is 120. Writing the cost of such a function as a recurrence like T(n) = T(n-1) + 1 is the first step toward predicting how it grows, without running a single call.
Using recursion to solve problems
Binary search is a recursive algorithm for finding an item in a sorted list. Look at the middle item. If it matches, you are done. If your target is smaller, search the left half; if larger, search the right half. Each call throws away half the list, so one step of constant work plus a search on n/2 items. Written as a recurrence, that is T(n) = T(n/2) + c. The famous Towers of Hanoi puzzle is another classic: moving n disks takes moving n-1 disks aside, moving the biggest disk, then moving the n-1 disks back, which gives T(n) = 2T(n-1) + 1. Both patterns, halving and shrinking by one, show up again and again when you analyze recursive algorithms.
Towers of Hanoi
The Towers of Hanoi puzzle gives you three pegs and n disks of different sizes, all stacked on one peg from largest at the bottom to smallest on top. The goal is to move the whole stack to another peg, moving one disk at a time and never placing a bigger disk on a smaller one. The recursive idea is beautiful. To move n disks from peg A to peg C, first move the top n-1 disks from A to B, then move the biggest disk from A to C, then move the n-1 disks from B to C. Counting the moves gives the recurrence T(n) = 2T(n-1) + 1 with T(1) = 1. Expanding it, each size costs one more than double the previous size, and the total comes out to 2^n - 1 moves. That exponential cost is why the legend says 64 disks would take longer than the age of the universe to move at one disk per second.
Improving efficiency of recursive functions
A recursive algorithm can be elegant and still be slow. When a function recomputes the same smaller subproblems over and over, the running time explodes. Think of computing a recursive quantity where the same call appears many times in the recursion tree: each repeated call repeats all of its own work. Two main tools fix this. Memoization saves each answer in a table so a repeated call returns instantly, which often collapses an exponential recurrence into a linear one. Or rewrite the recursion as iteration that builds up from small cases to large ones. Either way, the first step is the same: write the recurrence, draw or expand the tree, and count the repeated work before trying to speed it up.
2 · Watch
En anglaisTake it off screen
Where it sits
16 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.