Which property must a loop's termination measure have for the loop to be guaranteed to stop, not merely usually stop?
answer
- built from the loop's own state
- every pass, not most passes
- cannot descend forever
- an integer with a floor
- the equal pass is the hang
basics
~20 sThe measure must strictly decrease on every pass without exception and be bounded below, so it cannot fall forever. A measure that decreases on most passes proves nothing: the exceptional passes are exactly where a loop hangs.
solid answer
~50 sA termination measure is an expression over the loop's own state — not wall-clock time, not a retry counter bolted on — with two properties. It **strictly decreases on every pass**, and it **cannot decrease indefinitely**, in practice because it is an integer with a floor such as zero. Together those give a finite bound on the number of passes. The word doing the work is *every*: for a drain loop the natural measure is the number of records still beyond the cursor, and that measure fails the instant the source may return a page with no records and an unchanged cursor. On that pass nothing decreases, so the argument collapses even though the invariant is untouched. A loop like that is correct only if it happens to terminate — which is a property of the data it met, not of the code.
go deeper
Remember that something concrete has to get smaller every time round the loop, and that it must have a floor it cannot go below.
Name the measure for a given loop and identify the branch on which it might fail to decrease; explain why an average decrease proves nothing.
Diagnose a loop that hangs occasionally by writing the measure down, locating the pass that leaves it unchanged, and deciding whether it is a bug or an unstated assumption about the source.
Set the expectation that loops crossing a system boundary carry an enforceable progress check, so a broken upstream contract surfaces as a reported error rather than a stuck worker.
## What a measure is A **termination measure** (also called a variant) is an expression built from the loop's own variables whose value you can evaluate at the top of each pass. It exists to convert "does this loop end?" — a question about an unknown number of future passes — into a question about one pass, the same trick the invariant plays for correctness. Two obligations: 1. **Strict decrease on every pass.** If the guard is true and the body runs, the measure at the next top is strictly less than at this top. Not less-or-equal. Not less on average. 2. **Bounded below.** The values cannot descend forever. In practice this means a non-negative integer: a strictly decreasing sequence of non-negative integers has finitely many terms, so the loop has finitely many passes. (More general decreasing orders exist, but interviews and real code live on integers with a floor.) Miss either obligation and you have no proof — only a habit of observed behaviour. ## Why "decreases on most passes" is worthless Suppose the measure falls on every pass except when some condition holds. Then a loop that meets that condition repeatedly never ends, and nothing in the argument forbids it. The exceptional pass is not an edge case around the proof; it *is* the hang. This is the single most common way a termination argument is quietly wrong: the author checks the typical path, sees the counter move, and calls it done. A useful reflex: state the measure, then hunt for a pass on which it could stay equal. If you can construct one, you have found either the hang or the precondition you must enforce. ## Two loops, two measures | Loop | Measure | Strictly decreases when | Fails when | |---|---|---|---| | Draining a paged source into a sink | Records still beyond the cursor | Every page carries at least one record and the cursor advances past it | A page is empty, or the source hands back the same cursor | | Shrinking-window search over a sorted index | Window size, upper bound minus lower | Each pass moves one bound strictly past the midpoint side it discarded | An update leaves a bound where it was | Notice how different the two are in one respect: the second measure is made of the loop's own indices, so the proof is entirely yours. The first is made of a quantity a remote source controls, so it is a proof *conditional on a contract* — if that contract is only assumed, termination is assumed with it. ## Diagnosing a loop that is correct only if it happens to stop The signature is a loop whose invariant reviews cleanly, whose outputs are right whenever it finishes, and which occasionally does not finish. Work through it in this order. 1. **Write the measure down.** If nobody can name one, that is the finding: the loop has never had a termination argument, only a track record. 2. **Find the pass where it does not strictly fall.** Usually a branch that continues the loop without consuming anything — a retry that re-enters with identical state, a skip that leaves the cursor untouched, an update conditional on data that may not hold. 3. **Decide whether the missing decrease is a bug or an assumption.** A skip that forgets to advance is a bug. A source permitted to return an empty page is an assumption that was never written down. 4. **Make the decrease enforceable.** Assert that the measure fell — the cursor strictly advanced, the window strictly shrank — and fail loudly if it did not. That converts an unbounded hang into a reported error at the pass where the reasoning actually broke. ## What a measure is not - **Not elapsed time.** A deadline ends the process; it does not make the loop's own state descend, and a loop that is killed halfway has not terminated in the sense the proof needs. It is a containment device, not an argument. - **Not a retry counter added beside the real state.** A cap does bound the passes, but by abandoning the loop's postcondition rather than reaching it. That trade is sometimes right, and it should be made explicitly. - **Not a running-time bound.** A measure starting at a billion and falling by one per pass proves the loop stops and says nothing about whether it stops today. - **Not evidence from testing.** Tests show the measure fell on the inputs tried. The obligation quantifies over all of them. ## In an interview Name the measure explicitly, then name the pass that threatens it. "The measure is the number of unfetched records; it falls on every pass provided each page is non-empty, so I would either require that of the source or assert the cursor strictly advanced." That answer demonstrates both obligations and shows where the proof meets reality.
- Why does a deadline not count as a termination measure?Because it is not a function of the loop's state and its expiry does not make the loop reach its exit condition — it abandons the loop mid-flight, leaving the postcondition unproved. Deadlines are containment: they bound damage from a hang. The measure is what shows there is no hang to contain.
- Can a measure decrease by varying amounts on different passes?Yes. Strictness is the only requirement — any strictly decreasing sequence with a floor is finite, whether it falls by one or halves. A search window that shrinks by half and a cursor that advances by one page both qualify. How fast it falls is a running-time question, not a termination one.
- What is the cheapest way to make a suspect measure observable?Capture the measure at the top of the pass, recompute it at the bottom, and fail if it did not strictly decrease. The check costs a comparison and turns an unbounded hang into an error raised at the exact pass where the reasoning broke, with the state that broke it still in hand.
saying these in an interview costs you the question
- Accepts a measure that decreases on most passes
- Offers a wall-clock deadline as the termination argument
- Counts a retry cap as proof the loop terminates correctly
- Confuses a termination measure with a running-time bound
- Assumes a cursor always advances because it usually does
- Says the invariant would have caught the missing decrease