Practice question · Put in order
Order the three parts of a loop-invariant argument, which mirror mathematical induction.
- Maintenance: if true before an iteration, it stays true after it
- Initialization: the invariant is true before the first iteration
- Termination: the loop ends and the invariant implies the result
Hints
- The order matches induction: base case, inductive step, conclusion.
- You establish the property, show each step preserves it, then read off the result at the end.
Show the answer
- Initialization: the invariant is true before the first iteration
- Maintenance: if true before an iteration, it stays true after it
- Termination: the loop ends and the invariant implies the result
Why
Initialization, maintenance, termination, the same shape as a proof by induction. Establish the invariant, show every iteration preserves it, and its truth at the end proves the algorithm computed the right thing.
Practise Loop Invariants and Correctness Ideas
The app has 7 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.