Difficulty: Intermediate | Prerequisites: Familiarity with big-O notation, basic proof techniques (induction), recursion, and elementary data structures (arrays, binary trees).
This material sits early in EECS 376, covering the foundational algorithmic techniques you will use throughout the rest of the course and beyond. The potential method gives you a general-purpose tool for proving that loops terminate. Divide and conquer provides a design pattern for breaking hard problems into smaller ones, while the Master Theorem lets you read off the runtime of those algorithms without unrolling the recurrence by hand. If you are joining the course late or skipped the first few lectures on asymptotic notation and induction, revisit those before working through these notes.
The potential method proves an algorithm halts by finding a quantity that drops by a fixed amount each iteration and has a lower bound. Divide and conquer splits a problem into smaller copies of itself, solves them recursively, and merges the answers. The Master Theorem turns the resulting recurrence T(n) = k · T(n/b) + O(n^d) into a closed-form runtime by comparing k to b^d.
Potential function
A function s: A → ℝ that maps an algorithm's internal state to a real number, decreasing by at least a fixed positive constant C with every unit of work, and bounded below by some value B. Think of it as an energy meter that drains at a guaranteed rate, so the algorithm must eventually stop.
Divide and conquer
An algorithm design paradigm that breaks the input into smaller instances of the same problem, solves them recursively, and combines the results. In simple terms, you keep splitting until the problem is trivial, then stitch the answers back together.
Base case (divide and conquer)
The condition under which the algorithm stops recursing and returns a direct answer, typically when the input has size 0 or 1.
Recurrence relation
An equation expressing T(n) in terms of T for smaller inputs, capturing the cost of the recursive calls plus the combine step. In simple terms, it is a formula that says "the time to solve size n equals some copies of smaller sizes, plus the merge overhead."
Master Theorem
A closed-form recipe for solving recurrences of the form T(n) = k · T(n/b) + O(n^d). It gives you the asymptotic runtime by comparing k (the number of recursive calls) to b^d (the branching vs. the work per level). Think of it as a lookup table: plug in k, b, and d, compare, and read off the answer.
Inductive/recursive hypothesis
The assumption, used when proving correctness of a divide-and-conquer algorithm, that the recursive calls return correct outputs. This mirrors the inductive hypothesis in a mathematical induction proof.
Majority element
The element in an array A[1, ..., n] that appears strictly more than n/2 times, if such an element exists. Because more than half the slots hold the same value, there can be at most one majority element.
Local maximum (in a labelled tree)
A vertex whose label is greater than or equal to the labels of all its neighbours (parent and children). In simple terms, it is a node that is at least as large as everything directly touching it.
The potential method gives you a structured way to prove that an algorithm terminates, and to bound how many steps it takes. You define a real-valued function s over the algorithm's state (its variables at any moment), then show two things:
s decreases by at least some fixed constant C > 0 with every unit of work (e.g. every loop iteration).
s has a lower bound B, meaning the algorithm must stop once s ≤ B.
Once both conditions hold, the maximum number of work units is (I − B) / C, where I is the initial value of s.
When you face a "does this program halt?" question, your job is to either exhibit a valid potential function or exhibit an input sequence that keeps the program running forever.
Finding a potential function. Look at what changes each iteration. If some quantity always drops, use it directly. If two variables move in opposite directions, try a weighted combination. The potential function need not match any single variable; s = 2x + y or s = x are both fair game.
Showing non-termination. If you suspect the program can loop forever, construct a concrete input sequence that keeps the loop condition satisfied indefinitely. You need to show that for every iteration, you can choose the next input so that the loop condition remains true.
Exercise 1(a): halts
The program reads x, y > 0, then loops while x > 0 AND y > 0. Each iteration, if the new input z is even, x decreases by 1 (and y increases by 1). If z is odd, y decreases by 1. Use s = x as the potential function. When z is even, s drops by 1. When z is odd, y drops by 1 but x is unchanged, so s does not increase. But we need s to strictly decrease every iteration, and the odd branch leaves s unchanged. So s = x alone does not work directly.
Instead, use s = x + y. When z is even: x drops by 1, y rises by 1, so s stays the same. That also fails.
The correct approach: use s = x. In the even branch, s drops by 1 (C = 1). In the odd branch, s stays the same but y drops by 1. The loop requires both x > 0 and y > 0. After enough odd inputs, y will hit 0 and the loop exits, regardless of x. After enough even inputs, x will hit 0 and the loop exits. So consider the quantity s = x. It never increases, and every even-input iteration drops it by 1. If the adversary feeds only odd inputs forever, y will eventually hit 0 and the loop terminates. If even inputs appear infinitely often, x eventually hits 0. Either way, the program halts.
More precisely, the potential function s = x works with the following argument: s decreases by 1 every even-input iteration and stays the same on odd-input iterations. But a run of consecutive odd-input iterations is bounded by the current value of y (which decreases by 1 each time, with lower bound 0). So within at most y₀ odd iterations, either the loop exits (y hits 0) or the next iteration must be even (dropping x). The total iterations are at most x₀ · (y₀ + 1), where x₀ and y₀ are the initial values.
Exercise 1(b): does not halt
The difference from (a) is that the else branch now also sets x ← x + 1. With z even: x drops by 1, y rises by 1. With z odd: y drops by 1, x rises by 1. Use s = x + y: when z is even, s stays the same; when z is odd, s stays the same. So x + y is a conserved quantity. As long as the adversary alternates even and odd inputs, both x and y stay positive (they just swap mass back and forth). For example, with x₀ = 1, y₀ = 1, alternating even then odd inputs keeps x and y oscillating: (1,1) → (0,2) → (1,1) → (0,2) → ... But wait, x = 0 means the loop condition x > 0 fails. So the even branch takes x to 0, and the loop exits.
Actually, let us be more careful. Start with x₀ = 2, y₀ = 2. Feed even, odd, even, odd, ... : (2,2) → (1,3) → (2,2) → (1,3) → ... The loop condition x > 0 AND y > 0 is always satisfied. The program never halts. So (b) does not halt for all input sequences. A non-halting input sequence is: x₀ = 2, y₀ = 2, then alternate even and odd inputs forever.
Exercise 1(c): does not halt
The difference from (a) is the loop condition: while x > 0 OR y > 0 (instead of AND). The body is the same as (a). When z is even, x drops by 1 and y rises by 1. When z is odd, y drops by 1. The adversary can keep the loop alive by always feeding even inputs: x decreases by 1 each time, but y increases by 1 each time. Once x hits 0, the loop still runs because y > 0. Then feeding even inputs makes x = −1, −2, ... while y keeps growing. The condition y > 0 stays true forever.
A concrete non-halting sequence: x₀ = 1, y₀ = 1, then feed even inputs forever. After iteration 1: x = 0, y = 2. The loop continues (y > 0). After iteration 2: x = −1, y = 3. And so on.
A divide-and-conquer algorithm has three ingredients:
Base case. When the input is small enough (often size 0 or 1), return the answer directly.
Divide. Split the input into smaller subproblems, typically by a constant factor. For an array, this usually means splitting into halves; for a tree, taking left and right subtrees.
Conquer (combine). Merge the results of the recursive calls, possibly with additional processing, to produce the answer for the full input.
Designing the right split and the right combine step is where the creative thinking lives. A clever combine step can reduce the number of recursive calls needed (as in Karatsuba multiplication).
Correctness proofs for divide-and-conquer algorithms mirror strong induction:
Base case. Show that the algorithm produces the correct output when the input is small enough to be handled directly.
Inductive step. Assume the recursive calls return correct outputs (this is the inductive/recursive hypothesis). Then show that the combine step produces the correct output for the full input.
By strong induction, correctness on all input sizes follows.
Derive a recurrence relation for T(n), the running time on input of size n. Most divide-and-conquer algorithms yield a recurrence of the form:
T(n) = k · T(n/b) + O(n^d)
where k is the number of recursive calls, n/b is the size of each subproblem, and O(n^d) is the cost of the combine step. Then apply the Master Theorem to get a closed form.
Example: Mergesort. T(n) = 2T(n/2) + O(n). Here k = 2, b = 2, d = 1. Since k = b^d (2 = 2^1), the Master Theorem gives T(n) = O(n log n).
Given T(n) = k · T(n/b) + O(n^d), with constants k ≥ 1, b > 1, d ≥ 0:
Case 1 (k < b^d): T(n) = O(n^d). The combine step dominates. The recursion tree is top-heavy.
Case 2 (k = b^d): T(n) = O(n^d log n). Work is evenly spread across levels, so you pick up a log factor.
Case 3 (k > b^d): T(n) = O(n^(log_b k)). The recursive calls dominate. The recursion tree is bottom-heavy, and the exponent log_b k reflects the branching factor.
If the additive term is Θ(n^d) rather than O(n^d), the bounds tighten to Θ as well.
When the combine cost has a logarithmic factor, T(n) = k · T(n/b) + Θ(n^d log^w n), the theorem generalises:
k < b^d: T(n) = Θ(n^d log^w n)
k = b^d: T(n) = Θ(n^d log^(w+1) n)
k > b^d: T(n) = Θ(n^(log_b k))
Setting w = 0 recovers the ordinary Master Theorem.
Identify k (number of recursive calls), b (factor by which the input shrinks), and d (exponent of the combine cost). Compute b^d. Compare k to b^d. Read off the case.
Worked examples from the worksheet:
MajorityElement. The algorithm makes 2 recursive calls on subarrays of size n/2 (k = 2, b = 2). The combine step iterates over A at most twice, costing O(n) (d = 1). Since k = b^d (2 = 2^1), Case 2 applies: T(n) = O(n log n).
Algorithm A (naive 3-way integer multiplication). Splits each number into 3 pieces of size n/3, makes 9 recursive multiplications, and combines in O(n). So k = 9, b = 3, d = 1. Compare: b^d = 3^1 = 3. Since 9 > 3, Case 3 applies: T(n) = O(n^(log_3 9)) = O(n^2).
Algorithm B (super-Karatsuba). Same split into thirds, but only 5 recursive multiplications, combine in O(n). So k = 5, b = 3, d = 1. Compare: b^d = 3. Since 5 > 3, Case 3 applies: T(n) = O(n^(log_3 5)) ≈ O(n^1.465).
For reference, standard Karatsuba splits into halves with 3 multiplications: k = 3, b = 2, d = 1, giving T(n) = O(n^(log_2 3)) ≈ O(n^1.585). So Algorithm B is asymptotically faster than Karatsuba, while Algorithm A is asymptotically slower (quadratic).
The algorithm. MajorityElement(A[1..n]) works as follows: if n = 1, return A[1]. Otherwise, recursively find the majority element of each half. If the left half returns a candidate x ≠ ⊥, count x in the full array; if it appears more than n/2 times, return x. Repeat for the right half's candidate y. If neither works, return ⊥.
Runtime. Two recursive calls on arrays of size n/2, plus at most two linear scans of A. Recurrence: T(n) = 2T(n/2) + O(n). By the Master Theorem (k = 2, b = 2, d = 1, Case 2): T(n) = O(n log n).
Correctness. The key lemma: if z is the majority element of A[1..n], then z must be the majority element of at least one of A[1..n/2] or A[n/2+1..n].
Proof by contradiction: suppose z is the majority of neither half. Then z appears at most n/4 times in each half (at most half of each half). So z appears at most n/4 + n/4 = n/2 times total, contradicting the assumption that z appears strictly more than n/2 times.
Because of this lemma, the algorithm is guaranteed to consider any true majority element as a candidate (it will be returned by at least one recursive call). The full-array count then correctly verifies whether it truly is the majority.
Problem. Given a complete binary tree where each node has an integer label (queryable only by visiting), find a local maximum using O(log |V|) queries.
Algorithm. Start at the root. At the current node v, query v and all its children. If v's label is at least as large as all its children's labels, v is a local maximum; return it. Otherwise, move to the child with the largest label. Repeat.
Why it works. When you move to a child c whose label is larger than v's, you know c's label exceeds its parent's. So c is "more local-max-like" than v. Either c is already a local maximum (its label is at least as large as its own children), or one of its children is even larger, and you recurse downward. At a leaf, the node has no children, so it only needs to beat its parent, and it does (you moved there because it was larger). So the leaf is a local maximum.
Runtime. Each step moves one level down the tree and queries at most 3 nodes (the current node plus up to 2 children). A complete binary tree with |V| nodes has O(log |V|) levels. So the total number of queries is O(log |V|).
Potential method bound on work units:
Maximum iterations = (I − B) / C, where I = initial potential, B = lower bound, C = decrease per iteration.
General divide-and-conquer recurrence:
T(n) = k · T(n/b) + O(n^d)
Master Theorem cases:
k < b^d → T(n) = O(n^d)
k = b^d → T(n) = O(n^d log n)
k > b^d → T(n) = O(n^(log_b k))
Master Theorem with log factors: T(n) = k · T(n/b) + Θ(n^d log^w n)
k < b^d → Θ(n^d log^w n)
k = b^d → Θ(n^d log^(w+1) n)
k > b^d → Θ(n^(log_b k))
Mergesort: T(n) = 2T(n/2) + O(n) → O(n log n)
MajorityElement: T(n) = 2T(n/2) + O(n) → O(n log n)
3-way naive multiplication (Alg A): T(n) = 9T(n/3) + O(n) → O(n^2)
3-way super-Karatsuba (Alg B): T(n) = 5T(n/3) + O(n) → O(n^(log_3 5)) ≈ O(n^1.465)
Standard Karatsuba: T(n) = 3T(n/2) + O(n) → O(n^(log_2 3)) ≈ O(n^1.585)
The potential method is used in amortised analysis of data structures like dynamic arrays and splay trees, where individual operations can be expensive but the average cost over a sequence is low.
Divide and conquer underpins some of the most widely used algorithms in practice: Mergesort is the basis of most standard-library sorting routines, Karatsuba-style multiplication is built into big-integer libraries, and the closest-pair algorithm is used in computational geometry for collision detection and geographic information systems.
The Master Theorem saves significant effort in systems design. When choosing between algorithm variants (e.g. how many pieces to split an input into), you can quickly compare asymptotic runtimes to decide which approach scales better.
Students often think the potential function must be one of the algorithm's own variables (like x or y). It does not. It can be any function of the state, including a weighted sum or something the code never computes.
Students sometimes forget that the potential function must decrease by a fixed constant C every iteration. If it only decreases "eventually" or "on average," that is not sufficient for the standard potential method.
A common mistake with the Master Theorem is applying it to recurrences that do not fit the form T(n) = k · T(n/b) + O(n^d). For instance, SlowSort has the recurrence T(n) = 2T(n/2) + T(n − 1) + O(1), which involves different subproblem sizes. The Master Theorem does not apply here.
Students often confuse the majority element with the most frequent element. The majority element must appear strictly more than n/2 times. An array can have a most-frequent element without having a majority element at all (e.g. [1, 2, 3] has no majority element).
⚠️ You will almost certainly be asked to apply the Master Theorem to a new recurrence. Practise identifying k, b, and d quickly, and know which case applies.
⚠️ Potential function problems test whether you can construct the right function and argue its properties. Be ready to handle tricky cases where the obvious candidate (a single variable) does not work.
⚠️ Proving correctness of divide-and-conquer algorithms via induction is a staple exam topic. Make sure you can clearly state the inductive hypothesis and explain the base case.
⚠️ The majority element lemma (a majority element of the whole must be a majority element of at least one half) is a classic proof-by-contradiction pattern that appears in various forms.
True or false: A valid potential function must be one of the algorithm's own variables. (False. It can be any function of the state.)
Fill in the blank: If T(n) = 4T(n/2) + O(n), then by the Master Theorem, T(n) = O(______). (n^2, since k = 4 > b^d = 2^1 = 2, so Case 3 gives n^(log_2 4) = n^2.)
True or false: If an array has a most-frequent element, it necessarily has a majority element. (False. [1, 1, 2, 2, 3] has most-frequent elements 1 and 2, but no majority element.)
Fill in the blank: To prove a divide-and-conquer algorithm correct, the inductive step assumes that the ______ return correct results. (recursive calls)
True or false: The Master Theorem applies to T(n) = 2T(n/2) + T(n − 1) + O(1). (False. The subproblems are not all of the same form n/b.)
Q: A program reads positive integers x and y, then loops while x > 0 and y > 0. Each iteration, it reads z. If z is even, x ← x − 1 and y ← y + 1. If z is odd, y ← y − 1 and x ← x + 1. Does this program always halt? Justify your answer.
A: No. With initial values x = 2, y = 2 and alternating even/odd inputs, the state oscillates between (2, 2) and (1, 3) indefinitely, so the loop condition x > 0 AND y > 0 is always satisfied.
Q: State the three cases of the Master Theorem for T(n) = k · T(n/b) + O(n^d).
A: Case 1 (k < b^d): T(n) = O(n^d). Case 2 (k = b^d): T(n) = O(n^d log n). Case 3 (k > b^d): T(n) = O(n^(log_b k)).
Q: What is the recurrence and closed-form runtime for the MajorityElement algorithm?
A: T(n) = 2T(n/2) + O(n). By the Master Theorem (Case 2, since k = b^d = 2), T(n) = O(n log n).
Q: Prove that if z is the majority element of A[1..n], then z is the majority element of at least one of A[1..n/2] or A[n/2+1..n].
A: By contradiction. If z is not the majority of either half, then z appears at most n/4 times in each half, for a total of at most n/2. But z is the majority of the full array, so it appears strictly more than n/2 times. Contradiction.
Q: Describe an O(log |V|) algorithm to find a local maximum in a complete binary tree with integer labels.
A: Start at the root. Query the current node and its children. If the current node's label is at least as large as all children's labels, return it. Otherwise, move to the child with the largest label. Repeat. This descends at most O(log |V|) levels, querying at most 3 nodes per level.
Q: Algorithm A uses 9 recursive multiplications of n/3-digit numbers with linear combine. Algorithm B uses 5 such multiplications. Which is asymptotically faster, and how do both compare to Karatsuba?
A: Algorithm A: T(n) = 9T(n/3) + O(n) → O(n^2). Algorithm B: T(n) = 5T(n/3) + O(n) → O(n^(log_3 5)) ≈ O(n^1.465). Karatsuba: T(n) = 3T(n/2) + O(n) → O(n^(log_2 3)) ≈ O(n^1.585). Algorithm B is the fastest, then Karatsuba, then Algorithm A.
The potential method connects to amortised analysis, which you will encounter when studying data structures like dynamic arrays, hash tables, and splay trees. The idea of bounding total work by tracking a global quantity reappears in many forms.
Divide and conquer is the precursor to dynamic programming. Both decompose problems into subproblems, but dynamic programming handles overlapping subproblems by caching results. Recognising when subproblems overlap (DP territory) versus when they are independent (divide-and-conquer territory) is a recurring theme in algorithm design.
The Master Theorem connects to the broader topic of solving recurrences. More general techniques (the Akra-Bazzi method, recursion tree analysis) handle cases the Master Theorem cannot.
Potential method, potential function, amortised analysis, termination proof, loop invariant, divide and conquer, divide-and-conquer, D&C, recursive algorithm, base case, recursive case, conquer step, combine step, recurrence relation, Master Theorem, cookbook solution, asymptotic analysis, big-O, big-Theta, Mergesort, merge sort, Karatsuba multiplication, super-Karatsuba, majority element, Boyer-Moore voting, local maximum, binary tree, complete binary tree, closest pair, closest-pair algorithm, SlowSort, strong induction, recursive hypothesis, EECS 376, Foundations of Computer Science, University of Michigan