Difficulty: Intermediate | Prerequisites: Basic proof techniques, familiarity with recursion and Big-O notation
This set of notes covers three pillars of the EECS 376 midterm: writing recurrence relations for counting problems, using potential functions to prove that algorithms terminate, and applying the Master Theorem to determine the runtime of divide-and-conquer algorithms. If you can set up a recurrence from a word problem, pick the right potential function from a list, and solve a recurrence with the Master Theorem, you are in good shape for roughly 15-20 points of the exam.
Recurrence relation
A formula that defines each term of a sequence in terms of earlier terms, plus base cases. In this course, recurrences model counting problems (how many ways to tile, eat food, etc.) and algorithm runtimes.
In simple terms, it is an equation that says "the answer for size n depends on the answers for smaller sizes."
Potential function
A function Φ that maps the state of an algorithm to a non-negative integer, and strictly decreases with every iteration or recursive call. If such a function exists, the algorithm must halt because a non-negative integer cannot decrease forever.
Think of it as a fuel gauge: every step burns fuel, and when the tank hits zero the algorithm stops.
Master Theorem
A recipe for solving recurrences of the form T(n) = aT(n/b) + O(n^d). You compare log_b(a) to d and read off the answer. Three cases: if log_b(a) < d, the work at each level dominates and T(n) = O(n^d). If log_b(a) = d, every level contributes equally and T(n) = O(n^d log n). If log_b(a) > d, the leaves dominate and T(n) = O(n^(log_b(a))).
In simple terms, it tells you whether a divide-and-conquer algorithm spends most of its time splitting, merging, or both equally.
Base case
The smallest instance of a problem where the answer is known directly, without further recursion. Every valid recurrence needs at least one.
Halting
An algorithm halts if it always terminates in finite time on every valid input. To prove halting, you typically find a potential function that decreases each step and is bounded below.
The exam tests whether you can translate a word problem into a recurrence. The method is always the same: look at the last action, figure out what it "uses up," and sum over the distinct choices.
Setting up the recurrence
Identify every possible last move. Each move consumes some number of items (problems, tiles, steps).
For each move, the number of ways to finish the remaining items is W(n - cost_of_move).
If two moves have the same cost but are distinguishable (e.g. eating a tootsie roll vs. a cup of ice cream after doing 3 problems), they contribute separate terms.
Sum all the contributions.
Worked example (Exam Q1)
Andrew can: (i) do 1 problem + cookie, (ii) do 3 problems + tootsie roll, (iii) do 3 problems + ice cream.
Last move is option (i): the remaining n-1 problems can be finished in W(n-1) ways.
Last move is option (ii): remaining n-3 problems can be finished in W(n-3) ways.
Last move is option (iii): remaining n-3 problems can also be finished in W(n-3) ways.
So W(n) = W(n-1) + W(n-3) + W(n-3) = W(n-1) + 2W(n-3).
The correct answer is W(n) = W(n-1) + 2W(n-3).
Why the other options are wrong
W(n-1) + W(n-3) forgets that options (ii) and (iii) are different food choices, so it undercounts.
W(n-1) + W(n-2) + W(n-3) invents a "do 2 problems" option that does not exist.
W(n-1) + 3W(n-3) would mean three distinct 3-problem options, but there are only two.
W(n-1) + 3W(n-2) gets both the cost and the count wrong.
Base cases
You need base cases for n = 0, 1, and 2 (since the recurrence reaches back 3 steps). Typically W(0) = 1 (there is exactly one way to do nothing: do nothing), W(1) = 1 (one problem, one cookie), W(2) = 1 (two problems, two cookies, since the 3-problem options are not available).
A potential function Φ proves an algorithm halts if it satisfies three conditions: (1) Φ maps states to non-negative integers, (2) Φ strictly decreases on every loop iteration or recursive call, and (3) the algorithm terminates when Φ reaches its lower bound. If you can find such a Φ, the algorithm must halt because a non-negative integer cannot decrease infinitely.
Strategy for picking Φ from a list
For each candidate, check two things. First, does it stay non-negative throughout the loop? Second, does it strictly decrease on every possible path through the loop body? If either check fails on any execution path, discard that candidate.
Worked example: user-input loop (Exam Q2)
The loop runs while a < 376 and b < 376. Each iteration reads a user-specified positive integer c.
If c is odd: a decreases by 1, b increases by 1.
If c is even: a becomes b+2, then b becomes (the new a)+2, so both a and b jump to at least b+2 and b+4 respectively.
The tricky part: since the user controls c, we cannot predict which branch executes. The odd branch decreases a but increases b. The even branch can increase both a and b substantially.
Consider (376 - a) + 2(376 - b).
Odd branch: a goes down by 1 (so 376-a goes up by 1), b goes up by 1 (so 376-b goes down by 1). Net change = +1 + 2(-1) = -1. Strictly decreases.
Even branch: a = b+2, b_new = a_new + 2 = b+4. Both a and b increase (or stay large), so (376-a) and (376-b) both decrease. Net change is negative.
Non-negative: inside the loop, a < 376 and b < 376, so 376-a >= 1 and 376-b >= 1, making the function at least 3.
The correct answer is (376 - a) + 2(376 - b).
Why the other options fail
a + b: the even branch can increase both a and b, so a+b can increase.
376 - b: the odd branch increases b by 1, so 376-b decreases, which is good. But consider only this: does it always decrease? In the even branch, b jumps to b+4, so 376-b drops by 4, which is fine. But the problem is that in the odd branch, a decreases, and we need the loop to eventually end for a as well. 376-b alone does not track whether a reaches 376.
(376-a) + (376-b): in the odd branch, 376-a increases by 1 and 376-b decreases by 1, so the net change is 0. Not a strict decrease.
"May never halt": it can be shown to halt, so this is wrong.
Worked example: recursive ALG (Exam Q3)
ALG(a, b) where a, b are powers of 3. Base case: a=1 or b=1 or a=b returns 0. If a > b, recurse on (a/3, 3b). If b > a, recurse on (3a, b/3).
Note that a * b is unchanged by each recursive call: (a/3)(3b) = ab and (3a)(b/3) = ab. So ab is constant, not decreasing. That rules out ab.
Consider |b - a|. If a > b: new pair is (a/3, 3b). Since a and b are powers of 3 and a > b, we have a >= 3b. Then |3b - a/3| = |3b - a/3|. We need to check this decreases.
For a = 9, b = 1: |b-a| = 8. After call: (3, 3), |3-3| = 0. Decreased from 8 to 0. For a = 27, b = 1: |b-a| = 26. After call: (9, 3), |9-3| = 6. Decreased. For a = 27, b = 3: |b-a| = 24. After call: (9, 9), |9-9| = 0. Decreased.
The product a*b stays constant, but |b-a| shrinks toward 0 (where the base case a=b fires). The correct answer is |b - a|.
The Master Theorem solves recurrences of the form T(n) = aT(n/b) + O(n^d), where a is the number of subproblems, n/b is the size of each subproblem, and O(n^d) is the cost of the work done outside the recursive calls (the "combine" step).
The three cases
Case 1 (d > log_b(a)): the combine step dominates. T(n) = O(n^d).
Case 2 (d = log_b(a)): every level of the recursion does the same total work. T(n) = O(n^d log n).
Case 3 (d < log_b(a)): the leaves dominate. T(n) = O(n^(log_b(a))).
How to apply it
Identify a (number of recursive calls), b (factor by which input shrinks), and d (exponent of the combine cost).
Compute log_b(a).
Compare d to log_b(a) and read off the case.
Worked example (Exam Q5)
The new merge sort variant: 3 subproblems of size n/3, merge cost O(n^1.5).
So a = 3, b = 3, d = 1.5.
log_b(a) = log_3(3) = 1.
Since d = 1.5 > 1 = log_b(a), we are in Case 1: the combine step dominates.
T(n) = O(n^1.5).
The correct answer is O(n^1.5).
Students often confuse the number of distinct choices with the cost of each choice. In the Andrew food problem, two options both cost 3 problems, but they are different rewards, so they produce two separate W(n-3) terms, not one.
A potential function does not need to decrease by exactly 1 each step. It just needs to strictly decrease (by at least 1) and remain non-negative. A drop of 4 is perfectly fine.
When checking potential functions, students sometimes only verify one branch of an if-else. You must check every execution path through the loop body. If the function fails to decrease on even one path, it is not valid.
The Master Theorem only applies when every subproblem has the same size. If you have T(n) = T(n/3) + T(2n/3) + O(n), the Master Theorem does not apply directly.
Students sometimes mix up which case of the Master Theorem applies. Remember: if d > log_b(a), the combine dominates (Case 1). If d = log_b(a), you get the extra log factor (Case 2). If d < log_b(a), the leaves dominate (Case 3).
⚠️ Recurrence setup questions appear frequently. The exam gives you a word problem and 4-5 candidate recurrences. The trap is always double-counting or undercounting distinct options with the same cost.
⚠️ Potential function questions require you to verify all branches. The exam deliberately offers candidates that work on one branch but not the other.
⚠️ The "this algorithm may never halt" option is there to tempt you. In most exam questions, the algorithm does halt and the option is a distractor. Only pick it if you have a concrete counterexample showing non-termination.
⚠️ Master Theorem questions on this exam use clean numbers. If log_b(a) is not an integer, do not panic: just compute it and compare to d.
True or False: If an algorithm has two branches in a loop, and a candidate potential function decreases in one branch but stays the same in the other, it is still a valid potential function. (False: it must strictly decrease on every path.)
Fill in the blank: The Master Theorem applies to recurrences of the form T(n) = aT(n/b) + O(n^d). If d = log_b(a), then T(n) = O(______). (n^d log n)
True or False: W(n) = W(n-1) + W(n-3) correctly counts the ways Andrew can finish n problems when he has one option costing 1 problem and two distinct options each costing 3 problems. (False: the two 3-problem options give 2W(n-3), not W(n-3).)
Fill in the blank: To prove an algorithm halts, you need a function that maps each state to a ______ and strictly ______ on every iteration. (non-negative integer; decreases)
True or False: If ab remains constant across recursive calls, then ab is a valid potential function. (False: a potential function must strictly decrease, not stay constant.)
Q: You have a staircase with n steps. You can climb 1 step, 2 steps, or 4 steps at a time. Let C(n) be the number of distinct ways to reach the top. Write a recurrence for C(n) when n >= 4.
A: C(n) = C(n-1) + C(n-2) + C(n-4). Each term corresponds to one type of move. All three moves are distinct, and each costs a different number of steps, so each contributes exactly one term.
Q: Consider the function F(x, y) where x, y are positive integers. If x > y, recurse on F(x-y, y). If y > x, recurse on F(x, y-x). If x = y, return x. Identify a valid potential function proving F halts.
A: x + y. Each recursive call replaces the larger value with the difference, which is strictly smaller. Since x and y are positive integers, x + y is always positive and strictly decreases each call. (This is essentially Euclid's algorithm by subtraction.)
Q: A divide-and-conquer algorithm splits an input of size n into 4 subproblems of size n/2 and combines them in O(n) time. What is its runtime?
A: T(n) = 4T(n/2) + O(n). Here a = 4, b = 2, d = 1. log_2(4) = 2. Since d = 1 < 2 = log_b(a), we are in Case 3: T(n) = O(n^2).
Q: Same setup, but the combine step costs O(n^2). What is the runtime now?
A: Now d = 2 = log_2(4). Case 2 applies: T(n) = O(n^2 log n).
Recurrence relations reappear in the dynamic programming section of the course (see Q13 on the exam). The difference is that DP recurrences optimise a value (minimise cost, maximise profit), while counting recurrences sum up the number of ways. The structure of "look at the last choice and recurse on what remains" is identical.
Potential functions connect to loop invariants. A loop invariant tells you what is true at each iteration; a potential function tells you how much "work" is left. Both are tools for reasoning about loops, and the exam may ask you to use either one.
The Master Theorem is a special case of the more general Akra-Bazzi method, which handles unequal subproblem sizes. EECS 376 sticks to the standard Master Theorem.
Related Terms / Search Tags
recurrence, recurrence relation, counting recurrence, potential function, termination proof, halting proof, variant function, loop variant, Master Theorem, divide and conquer, runtime analysis, asymptotic complexity, Big-O, T(n), W(n), base case, recursive case, EECS 376, Foundations of Computer Science, University of Michigan, Winter 2026 midterm