Loop Invariant definition
A loop invariant is a statement that holds before each iteration of a loop at a specified point in the procedure.
Loop Invariant in a picture
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
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.
