Difficulty: Intermediate | Prerequisites: basic proof techniques (induction), familiarity with binary representations of integers, modular arithmetic basics.
This material covers two foundational questions in theoretical computer science: how do we prove that an algorithm terminates, and how do we bound the number of steps it takes? The core technique is the potential function, a mapping from a program's state to a number that strictly decreases on every iteration and is bounded below. If you can define such a function, the algorithm must halt. These ideas appear throughout EECS 376 and form the backbone of reasoning about correctness and efficiency of algorithms. You should already be comfortable with mathematical induction and basic summation identities.
Potential functions let you prove an algorithm terminates by showing some quantity drops every iteration and can never go below zero. The Euclidean algorithm computes GCDs efficiently, with its potential shrinking by at least a factor of 2/3 each step, giving O(log(x + y)) iterations. Consecutive Fibonacci numbers are the worst-case inputs for the Euclidean algorithm.
Potential function
A function that maps the state of an algorithm at each step to a non-negative value, used to prove termination or bound running time. In simple terms, think of it as a "fuel gauge" for the algorithm: if it drops every step and can never go negative, the algorithm must eventually stop.
Termination
The property that an algorithm halts (finishes running) on every valid input, rather than looping forever. In simple terms, this means the program always produces an answer and does not run indefinitely.
Strictly decreasing
A sequence or function where each successive value is smaller than the one before it. In simple terms, the number keeps going down, never stays flat or goes back up.
Loop invariant
A property that holds true before and after every iteration of a loop, used to reason about correctness. Think of it as a promise the loop keeps every time it runs.
Greatest common divisor (GCD)
The largest positive integer that divides both x and y with no remainder. Formally, gcd(x, y) = max{d : d | x and d | y}. In simple terms, it is the biggest number that goes evenly into both.
Euclidean algorithm
A method for computing gcd(x, y) by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller, until the remainder is zero. In simple terms, you keep dividing and taking remainders until one of them hits zero, and the other is your GCD.
Fibonacci sequence
The sequence 1, 1, 2, 3, 5, 8, 13, 21, ... where each term is the sum of the two preceding terms. In simple terms, you get the next number by adding the last two together. These represent the worst-case inputs for the Euclidean algorithm.
Consider a global array B[1...376] of bits and the following loop:
Find the largest index i where B[i] = 1.
If no such i exists, return 0 (halt).
Otherwise, set B[i] = 0 and set B[j] = 1 for all j from i+1 to 376.
The question: can any initial configuration of B make this loop run forever?
The algorithm treats B as a 376-bit unsigned integer b, and each iteration subtracts exactly 1 from it. Since b is a non-negative integer that strictly decreases on every step, and the algorithm halts when b = 0, the loop must terminate for any starting array.
That informal argument is sufficient, but the formal proof uses a potential function.
Define the potential function on the state of B at iteration i:
p(B_i) = \sum_{j=0}^{376} 2^{376-j} B_i[j]This is simply the value of B read as a binary number. The algorithm halts when p(B) = 0.
To prove termination, show that the potential strictly decreases each iteration. Let k be the largest index where B_i[k] = 1. The algorithm sets B_i[k] to 0 and all bits to the right to 1.
The change in potential is:
p(B_i) - p(B_{i+1}) = 2^{376-k} - \sum_{j=0}^{376-k-1} 2^j = 2^m - (2^m - 1) = 1where m = 376 - k.
The potential drops by exactly 1 each iteration and is bounded below by 0. Therefore the algorithm halts after at most p(B_0) iterations.
To prove any loop terminates:
Define a potential function p that maps the program state to a non-negative integer (or value from a well-ordered set).
Show p strictly decreases on every iteration.
Show the algorithm halts when p reaches its minimum.
If all three hold, the loop must terminate.
The Euclidean algorithm computes gcd(x, y) by repeated division:
Given (x, y) with x > y >= 0, write x = qy + r where 0 <= r < y.
Replace (x, y) with (y, r).
Repeat until r = 0. The last non-zero remainder is the GCD.
Example: gcd(33, 55) = gcd(55, 33) = gcd(33, 22) = gcd(22, 11) = gcd(11, 0) = 11.
Define the potential at step i as:
s_i = a_i + b_iwhere (a_i, b_i) is the pair of arguments at step i. The key property is that the potential shrinks by at least a factor of 2/3 at every step:
\frac{s_{i+1}}{s_i} \leq \frac{2}{3}This means the potential decreases exponentially. Since the algorithm starts with s_0 = x + y and halts when one argument reaches 0, the number of iterations is at most log_{3/2}(x + y), which is O(log(x + y)).
At each step, (a, b) becomes (b, a mod b). So s_{i+1} = b + (a mod b). Since a mod b < b, and also a mod b <= a - b (because a = qb + r with q >= 1), we get:
s_{i+1} = b + r \leq b + (a - b) = a < a + b = s_iThe tighter 2/3 bound comes from the fact that r < b, so s_{i+1} = b + r < 2b. Meanwhile s_i = a + b >= 2b + r (since a >= b + r when q >= 1), giving s_{i+1}/s_i <= 2b / (2b + r) < 2/3 when q = 1, and even smaller when q >= 2.
The Euclidean algorithm takes the most steps when the quotient q is always 1, meaning every step does y = 1 * x + r, so the sequence of arguments forms a Fibonacci-like sequence in reverse.
Consecutive Fibonacci numbers (e.g., 610 and 987) produce the maximum number of iterations for inputs of that size. In the homework example, gcd(610, 987) takes 14 iterations, and the ratio s_{i+1}/s_i hovers near 0.618 (the golden ratio minus 1) throughout, which is the slowest possible decay while still staying under 2/3.
Bit-array potential function:
p(B_i) = \sum_{j=0}^{376} 2^{376-j} B_i[j]Potential decrease per iteration (bit-array problem):
p(B_i) - p(B_{i+1}) = 2^m - (2^m - 1) = 1 \quad \text{where } m = 376 - kEuclidean algorithm potential:
s_i = a_i + b_iPotential ratio bound (Euclidean algorithm):
\frac{s_{i+1}}{s_i} \leq \frac{2}{3}Upper bound on Euclidean algorithm iterations:
\text{iterations} \leq \log_{3/2}(x + y) = O(\log(x + y))Geometric sum identity (used in the bit-array proof):
\sum_{j=0}^{m-1} 2^j = 2^m - 1Potential functions are not just a proof trick for homework problems. They are the standard technique for amortised analysis in data structures (splay trees, dynamic arrays, Fibonacci heaps all use them to prove average-case bounds). The Euclidean algorithm itself is used in cryptography, particularly in RSA key generation and computing modular inverses, which rely on the Extended Euclidean Algorithm covered in later problems.
Students often think the bit-array algorithm runs forever because it sets many bits to 1 on each iteration. It does not. The value interpreted as a binary integer still drops by exactly 1 each time, so termination is guaranteed.
Students sometimes confuse "potential function" with "loop invariant." A loop invariant is a property that stays true across iterations. A potential function is a quantity that changes (decreases) across iterations. They serve different purposes, though both help reason about loops.
A common error is believing the Euclidean algorithm's running time is O(min(x, y)). It is actually O(log(x + y)), which is much faster. The potential shrinks geometrically, not linearly.
Students sometimes think any pair of large numbers is a worst case for the Euclidean algorithm. In fact, only Fibonacci-like pairs (where the quotient is always 1) approach the upper bound. Pairs where one number is much larger than the other terminate very quickly.
⚠️ Defining a valid potential function is the standard method for proving termination. Expect to be asked to construct one for an unfamiliar algorithm.
⚠️ The 2/3 bound on the Euclidean algorithm is a commonly tested derivation. Know how to show s_{i+1}/s_i <= 2/3.
⚠️ Be prepared to identify worst-case inputs for the Euclidean algorithm. The answer is always consecutive Fibonacci numbers.
⚠️ The geometric sum identity (sum of 2^j from j=0 to m-1 equals 2^m - 1) appears repeatedly in these proofs. Have it memorised.
True or false: A potential function must map to a non-negative integer. True (or at least to a value from a well-ordered set bounded below).
Fill in the blank: The bit-array subtraction algorithm's potential decreases by exactly ___ on each iteration. 1.
True or false: The Euclidean algorithm's running time is O(x + y). False (it is O(log(x + y))).
Fill in the blank: The worst-case inputs for the Euclidean algorithm are consecutive ___ numbers. Fibonacci.
True or false: If B is the all-zeros array, the bit-array algorithm runs for 2^376 steps. False (it halts immediately because no index i with B[i] = 1 exists).
Q: Describe the three conditions needed to prove an algorithm terminates using a potential function.
A: (1) Define a function mapping the program state to a non-negative value. (2) Show the function strictly decreases on every iteration. (3) Show the algorithm halts when the function reaches its minimum.
Q: For the bit-array algorithm with B[1...376], what is the maximum number of iterations before it halts?
A: 2^376 - 1, which occurs when B is initially all ones. The potential starts at 2^376 - 1 and decreases by 1 each step.
Q: Compute gcd(103, 62) using the Euclidean algorithm. How many iterations does it take?
A: gcd(103, 62) = gcd(62, 41) = gcd(41, 21) = gcd(21, 20) = gcd(20, 1) = gcd(1, 0) = 1. It takes 5 iterations (after the initial swap).
Q: Why are consecutive Fibonacci numbers the worst case for the Euclidean algorithm?
A: Because the quotient q is always 1, meaning the remainder is as large as possible relative to the divisor at every step. This makes the potential s_i shrink as slowly as possible (by the golden ratio factor, approximately 0.618, which is close to the upper bound of 2/3).
Q: If gcd(x, y) is computed in k steps, what can you say about x + y?
A: x + y >= (3/2)^k, equivalently k <= log_{3/2}(x + y). This follows from the potential shrinking by at most a factor of 2/3 each step.
Potential functions reappear in amortised analysis (EECS 376/477), where they prove that expensive operations are "paid for" by cheap ones. The Euclidean algorithm is the foundation for the Extended Euclidean Algorithm and modular inverses (Problem 3 in this homework), which are central to RSA encryption and other number-theoretic cryptography. The Fibonacci connection links to the analysis of algorithms more broadly: Fibonacci numbers appear as worst cases in many divide-and-conquer and greedy algorithms.
Algorithm termination, potential function, loop termination proof, bit array subtraction, binary decrement, Euclidean algorithm, GCD, greatest common divisor, potential function analysis, 2/3 bound, Fibonacci worst case, amortised analysis, EECS 376 Homework 1, University of Michigan, Foundations of Computer Science, well-ordering principle, strictly decreasing function, geometric sum