Algorithms / Invariants And Structures
Least You Need to Know: Invariants and Structural Induction
Loop invariants explain why iterative algorithms stay correct after every update. Structural induction is the matching proof idea for recursive data structures such as lists and trees.
The least you need to know
- A loop invariant should be true before the loop starts, preserved by each iteration, and strong enough to prove the postcondition at the end.
- Invariants are about correctness, not just runtime.
- Structural induction proves a property for a recursive data structure by proving it for smaller substructures.
- Recursive lists and trees are natural settings for structural induction.
- Program reasoning often alternates between iterative invariants and recursive induction.
Key notation
invariant
property preserved by every loop iteration
base case
smallest structure or initial state
inductive / recursive step
prove the property for a structure from its smaller pieces
Tiny worked example
- In a prefix-sum loop, a good invariant is: after `k` iterations, the running total equals the sum of the first `k` array entries.
- At the end, `k=n`, so the running total equals the whole-array sum.
- Structural induction plays the same role for recursive definitions of lists and trees.
Common mistakes
- Students often choose a statement that is true only at the end rather than during every iteration.
- Students often forget to check initialization before the first loop iteration.
- Students often use ordinary numeric induction when the object is really a recursive structure.
How to recognize this kind of problem
- Ask what remains true after every loop update.
- A good invariant should mention the part of the input processed so far.
- If the object is recursively built from smaller objects, structural induction is a natural proof tool.
Next recommended lesson
Continue through this topic with Least You Need to Know: Lowest Common Ancestors and Path Intersections.
Least You Need to Know: Lowest Common Ancestors and Path IntersectionsRelated lessons
Keep going with nearby lessons in the same topic.