Loop variant

Key takeaways

Loop variant belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Loop variant to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Loop variant from memory before moving on to harder problems.

Reference excerpt

In computer science, a loop variant is a mathematical function defined on the state space of a computer program whose value is monotonically decreased with respect to a (strict) well-founded relation by the iteration of a while loop under some invariant conditions, thereby ensuring its termination. A loop variant whose range is restricted to the non-negative integers is also known as a bound function, because in this case it provides a trivial upper bound on the number of iterations of a loop before it terminates. However, a loop variant may be transfinite, and thus is not necessarily restricted to integer values. A well-founded relation is characterized by the existence of a minimal element of every non-empty subset of its domain. The existence of a variant proves the termination of a while loop in a computer program by well-founded descent. A basic property of a well-founded relation is that it has no infinite descending chains. Therefore a loop possessing a variant will terminate after a finite number of iterations, as long as its body terminates each time. A while loop, or, more generally, a computer program that may contain while loops, is said to be totally correct if it is partially correct and it terminates.

Rule of inference for total correctness In order to formally state the rule of inference for the termination of a while loop we have demonstrated above, recall that in Floyd–Hoare logic, the rule for expressing the partial correctness of a while loop is:

{ I ∧ C } S { I } { I } w h i l e C d o S { I ∧ ¬ C } , {\displaystyle {\frac {\{I\land C\}\;S\;\{I\}}{\{I\}\;{\mathtt {while}}\;C\;{\mathtt {do}}\;S\;\{I\land \lnot C\}}},}

where I is the invariant, C is the condition, and S is the body of the loop. To express total correctness, we write instead:

< is well-founded , [ I ∧ C ∧ V = z ] S [ I ∧ V < z ] [ I ] w h i l e C d o S [ I ∧ ¬ C ] , {\displaystyle {\frac {<{\text{ is well-founded}},\;[I\land C\land V=z]\;S\;[I\land V<z]}{[I]\;{\mathtt {while}}\;C\;{\mathtt {do}}\;S\;[I\land \lnot C]}},}

where, in addition, V is the variant, and by convention the unbound symbol z is taken to be universally quantified.

Every loop that terminates has a variant The existence of a variant implies that a while loop terminates. It may seem surprising, but the converse is true, as well, as long as we assume the axiom of choice: every while loop that terminates (given its invariant) has a variant. To prove this, assume that the loop

w h i l e C d o S {\displaystyle {\mathtt {while}}\;C\;{\mathtt {do}}\;S}

terminates given the invariant I where we have the total correctness assertion

[ I ∧ C ] S [ I ] . {\displaystyle [I\land C]\;S\;[I].}

Consider the "successor" relation on the state space Σ induced by the execution of the statement S from a state satisfying both the invariant I and the condition C. That is, we say that a state σ′ is a "successor" of σ if and only if

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Loop variant

Start with the simplest possible case. Write down what Loop variant claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Loop variant before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Loop variant ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Loop variant

In research: Loop variant appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Loop variant in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Loop variant is common in secondary-school and first-year university syllabi. It links to neighbouring topics Control flow, Formal methods, so understanding it makes those chapters shorter.
In everyday life: Look for Loop variant outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Loop variant in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Loop variant means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Loop variant out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Loop variant in simple terms?

In computer science, a loop variant is a mathematical function defined on the state space of a computer program whose value is monotonically decreased with respect to a (strict) well-founded relation by the iteration of a while loop under some invariant conditions, thereby ensuring its termination…

Why does Loop variant matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Loop variant?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Loop variant.