Loop Invariants and Proving an Algorithm Correct
A loop invariant is a statement that holds before a loop starts, survives every pass, and gives the wanted result once the loop stops. Stating one turns the claim that code seems to work into an argument that it works on every input.
What a learner can do afterwards
- State the invariant for an insertion sort and check it at entry, after a pass, and at exit
- Use an invariant to argue a summing loop is right for a list of any length
- Find the input that breaks a proposed invariant and repair the statement
1 · Read
A correct algorithm does two things: it gives the right answer for every allowed input, and it stops instead of running forever. Testing builds confidence because it is great at finding mistakes. But testing can never prove you right, since one more untried input always waits, and it might be the one where your code fails.
The tool for proof is a loop invariant. It is a statement that is true before the loop starts, stays true after every single pass, and turns into exactly what you want when the loop ends. Picture a rule that holds at the bottom of a ladder and survives every rung: then it must hold at the top too.
Sort cards by repeatedly selecting the smallest that remains and swapping it into the next spot. After step k, the first k cards are the k smallest, sitting in order: true at the start, kept true by each swap, and the whole hand is sorted at the end. Insertion sort keeps the same style of promise over the cards handled so far, and a summing loop promises that the running total equals the sum of the items seen so far.
Always ask what makes a while loop stop. Halving an even number again and again ends for 16, which falls to 8, 4, 2 and then 1, but it never ends for 0, because 0 is even and half of 0 is still 0. Repair the claim by adding that 0 is not allowed. A loop that counts down from 5 prints 5, 4, 3, 2 and 1, then meets 0 and stops on its own.
State what holds before, during and after your loop, and the final result follows for every input.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.