Problem Solving

Loop Invariant

Children move colored tiles around a path while tracking a group.

Loop Invariant definition

A loop invariant is a statement that holds before each iteration of a loop at a specified point in the procedure.

In Spanish
invariante de bucle
Topic
Algorithms and problem-solving

Loop Invariant in a picture

Loop Invariant diagramBefore adding the next number, the running total equals the sum of the numbers already processed.Start: total = 0The sum of no processed values is 0Process one more valueAdding it preserves the running-sum statementStop after the last valueThe invariant then gives the total of the full list
Before adding the next number, the running total equals the sum of the numbers already processed.

How it works

Show the statement holds before the first iteration. Then show that if it holds before an iteration, the loop body preserves it for the next one. When the loop terminates, use the invariant and the stopping condition to justify the result.

Worked examples

What invariant can track the largest value seen so far?

After processing k items, the stored maximum equals the largest of those k items.

Does an invariant alone prove a loop stops?

No. Termination needs a separate argument.

Why check the invariant before the first pass?

Initialization supplies the starting truth needed for the preservation argument.

Common mistake

Name the exact point in the loop where the statement holds. It can temporarily change during the loop body before being restored.

Quick check

What must a loop body do to its invariant by the next check?

Can the value of a variable change while an invariant statement stays true?

Show answer

Yes. The statement can describe a relationship among changing values.

When is the invariant used to justify the result?

Show answer

At termination, together with the stopping condition.

Sources

Flashcard

Loop Invariant

Reveal the definition

A loop invariant is a statement that holds before each iteration of a loop at a specified point in the procedure.

Effortless Math. “Loop Invariant.” Math Dictionary.