Difficulty: Introductory | Prerequisites: Basic understanding of binary representation, loops, and mathematical induction.
This topic sits at the very start of EECS 376 and introduces how to reason formally about whether a program will stop running. It belongs to the broader area of algorithm analysis: before you can ask "how fast is this program?", you need to know "does it even finish?" You should be comfortable with loops, arrays of bits, and the idea of a mathematical proof by contradiction. If you have seen induction before, that helps, but the core technique here (potential functions) is introduced from scratch.
To prove a loop must terminate, assign it a "potential": a non-negative integer value that strictly decreases every iteration. Because a non-negative integer cannot decrease forever, the loop must eventually stop. The bit-array program in this problem looks like it could run forever, but interpreting the array as a binary number shows that each iteration reduces this number by at least 1, so it always halts.
Termination
A program terminates if it eventually reaches a return or exit statement for every possible input. In simple terms, the program stops running rather than looping forever.
Potential function (loop variant)
A function that maps the current state of a program to a non-negative integer and strictly decreases with every iteration of a loop. Think of it as an energy meter that drains each time the loop runs: once it hits zero, the loop has no choice but to stop.
Bit array
A fixed-length array whose entries are each either 0 or 1. In this context, B[1..376] is a 376-element bit array.
Binary interpretation of a bit array
Treating the bit array B[1..n] as a binary number, where B[1] is the most significant bit and B[n] is the least significant bit. The resulting number ranges from 0 (all zeros) to 2^n - 1 (all ones).
Strictly decreasing
A sequence where each term is smaller than the one before it. If a non-negative integer sequence is strictly decreasing, it must eventually reach zero and cannot continue beyond that.
The program operates on a global array B[1..376] where each entry is 0 or 1. Each iteration of the while-true loop does the following:
Find the largest index i where B[i] = 1.
If no such index exists (the array is all zeros), return 0 and halt.
Otherwise, set B[i] to 0, then set every entry from B[i+1] through B[376] to 1.
At first glance, the program looks like it might run forever. Setting all those trailing bits to 1 seems to "add" a lot of ones to the array. But the key insight is that the highest 1-bit moves to a lower index each iteration.
Define the potential as the integer you get by reading B[1..376] as a binary number:
Φ(B) = B[1] · 2^375 + B[2] · 2^374 + ... + B[376] · 2^0
This potential is always a non-negative integer (it is zero exactly when the array is all zeros).
Now consider what happens in one iteration. The program finds the largest i with B[i] = 1 and:
Clears B[i], subtracting 2^(376 - i) from the potential.
Sets B[i+1] through B[376] to 1, adding at most 2^(376 - i - 1) + 2^(376 - i - 2) + ... + 2^0 = 2^(376 - i) - 1.
The net change is at most -2^(376 - i) + (2^(376 - i) - 1) = -1. So the potential drops by at least 1 every iteration.
Since Φ(B) starts at some finite non-negative integer and decreases by at least 1 each step, the loop can run at most Φ(B_initial) times before the potential hits zero, at which point the array is all zeros and the program returns.
This argument is a template you will use repeatedly in EECS 376:
Identify a quantity (the potential) that maps each program state to a non-negative integer.
Show the quantity strictly decreases each iteration.
Conclude the loop runs at most (initial potential) times.
The hardest step is usually finding the right potential function. In this problem the binary interpretation of the array is the natural choice, but in other problems you may need to be more creative.
Potential of the bit array:
Φ(B) = Σ (from k=1 to 376) B[k] · 2^(376 - k)
Geometric series identity (used in the proof):
2^0 + 2^1 + ... + 2^(m-1) = 2^m - 1
This identity is why setting all trailing bits to 1 adds strictly less than the value removed by clearing one bit.
Potential function arguments show up wherever you need to guarantee that a process finishes. Garbage collectors in programming languages use similar reasoning to prove that memory reclamation terminates. Network routing protocols argue convergence by showing that a global metric strictly decreases with each update. Any time you hear "this system eventually reaches a stable state," there is usually a potential function lurking behind the claim.
Students often think the program runs forever because the loop sets many bits to 1 each iteration. It does not run forever: the value removed (one high bit) always outweighs the value added (many lower bits), thanks to the geometric series identity.
Students sometimes confuse "the array has more 1-bits" with "the potential is higher." The count of 1-bits is not the right potential here. A single 1 in a high position is worth more than many 1s in low positions.
A common mistake is choosing a potential that is not strictly decreasing. If your potential can stay flat on some iteration, the argument breaks. You need strict decrease every step.
Some students try to argue termination by tracking the position of the highest 1-bit alone. That does not work either, because the highest 1-bit can stay at the same position for multiple iterations (consider what happens when B[i] = 0 but B[i+1] = 1).
⚠️ Potential function arguments are a staple of EECS 376 exams. Expect to be given a novel loop and asked to prove it terminates.
⚠️ The examiner may give a program where the obvious "count" does not decrease. The skill is choosing the right mapping from state to integer.
⚠️ Know the geometric series sum cold. It appears in termination proofs, running-time analysis, and probability arguments throughout the course.
True or false: If a loop's potential function can stay the same on some iteration, the termination argument still works. (False: the potential must strictly decrease every iteration.)
Fill in the blank: The sum 2^0 + 2^1 + ... + 2^(n-1) equals ___. (2^n - 1)
True or false: The bit-array program can run forever if the initial array is all ones. (False: the potential starts at 2^376 - 1 and decreases by at least 1 each step.)
Fill in the blank: A valid potential function maps each program state to a ___ integer. (non-negative)
Q: A program maintains a counter c that starts at some positive integer. Each iteration, the program either decrements c by 1 or sets c to 2c. Does the program necessarily terminate? Why or why not?
A: No. The potential c is not guaranteed to decrease: the operation c → 2c increases it. A potential function must strictly decrease every iteration for the termination argument to apply.
Q: Consider the bit-array program with B[1..376]. What is the maximum number of iterations the program can execute?
A: The maximum potential is 2^376 - 1 (when every bit is 1). Since the potential decreases by at least 1 per iteration, the program executes at most 2^376 - 1 iterations.
Q: Suppose the program is modified so that line 7 sets B[j] to 0 instead of 1. Does the modified program terminate? What is the potential function argument?
A: Yes. Each iteration simply clears B[i] and all entries after it. The number of 1-bits in the array strictly decreases each iteration (by at least 1), so the number of 1-bits is itself a valid potential function.
This connects directly to running-time analysis: once you know a loop terminates, the potential function often gives you an upper bound on the number of iterations, which feeds into Big-O analysis. The Euclidean algorithm (covered next in this homework) uses an analogous argument where the potential is the sum of the two inputs and it drops by a factor of at least 2/3 each iteration. Later in the course, amortised analysis generalises the idea of a potential function to sequences of operations rather than single loops.
Program termination, loop termination proof, potential function, loop variant, loop bound, bit array binary interpretation, geometric series, strictly decreasing sequence, well-ordering principle, termination argument, EECS 376, foundations of computer science, algorithm halting, non-negative integer descent