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.
More to read
Verifying an algorithm
A good algorithm does two things: it gives the right answer for every allowed input, and it stops instead of running forever. Together these are called correctness.
Programmers often try to build confidence by testing. They run the code on a few inputs and watch the results. This is called empirical analysis, and it is great for finding mistakes. But testing can never prove a program is right. No matter how many inputs you try, there is always one more you have not tried, and that one might be the input where the code fails.
To really prove correctness, you need formal reasoning. That means making a careful logical argument about what the code does, not just watching it run. One of the most useful tools for loops is a loop invariant: a statement that is true before the loop starts, stays true after every pass, and turns into exactly what you want when the loop ends.
Think of it like a rule that holds at every step of climbing a ladder. If the rule holds at the bottom, and every rung keeps it true, then it must hold at the top too. That is the whole trick. Testing says the ladder worked the times you climbed it. An invariant proves it will work every single time.
Selection sort pseudocode
Imagine a hand of shuffled cards you want in order from smallest to largest. Selection sort is a simple way to do it, step by step:
1. Find the smallest card in the whole hand. Swap it with the first card. 2. Find the next smallest card. Swap it with the second card. 3. Keep going: find the next smallest and swap it into the next spot. 4. Repeat until every card is in place.
It is called selection sort because each step selects the smallest remaining card.
After you finish step k, the first k cards are always the k smallest cards, sitting in order. That statement is true before you begin (zero cards are trivially sorted), and every swap keeps it true. So when you have done every step, the statement says the whole hand is sorted. That is a loop invariant doing its job: true at the start, kept true by each pass, and it gives you the final result.
Docs: loops
Loops let a program repeat work without writing the same lines again and again. Python has two main kinds.
A while loop repeats a block of code as long as its condition is True. The condition can be any expression that gives a yes or no answer. Each time the block finishes, the condition is checked again, and the loop only continues if it is still True.
A for loop repeats once for each item in a sequence, like each number in a range. It runs a set number of times, which makes it easier to predict.
Why does this matter for proving code correct? Because every loop is a promise: when it stops, something useful should be true. With a while loop, you must ask what makes the condition finally become False, or the loop could run forever. With a for loop, you know how many passes happen, so you can say what is true after each one. A loop invariant is just a careful statement of that promise, checked at the start, after every pass, and at the end.
2 · Watch
به انگلیسیTake it off screen
Where it sits
10 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.