Loop Invariants

This concept is the first step toward proving that the programs you write — and the algorithms inside AI systems — actually do what they claim. You will use loop invariants later when you study Binary Search (correctness depends entirely on maintaining the invariant), Merge Sort and Quicksort (the invariant holds through every merge and partition), and Dynamic Programming (each subproblem solution must satisfy its own invariant). It also sharpens the way you read code: every while loop you see in a library or framework becomes a claim you can check. Mastering this unlocks the next topic: Big-O Notation, where you will analyse how fast an algorithm runs, and eventually Data Structures where invariants guarantee that operations like 'find the smallest' are always correct.

Imagine you are baking a cake and you have a recipe with several steps. You want to be sure that after each step, some condition holds — say, 'the oven is preheated to 180°C'. Before you start, you check the oven and it is indeed preheated. Then you follow each step, and after every single step you check again: still 180°C. At the end, you know for certain that the cake went into a properly heated oven. The condition 'the oven is at 180°C' is true before the first step, and it remains true after every step. That is exactly a loop invariant: a statement that is true at the start, and stays true every time you go around the loop. In programming, loops repeat an action many times. A loop invariant is a promise that, no matter how many times the loop runs, a certain property does not change. If you can show three things — that the invariant holds before the loop starts, that it holds after each iteration (assuming it held before), and that the loop eventually stops — then you have proven the loop does what you wanted. This is not just a nice theory: it is how you catch bugs before you even run the program. For example, suppose you are summing a list of numbers. The invariant might be 'the total so far is the sum of the first i numbers'. At the start, i=0, the total is 0, and the sum of zero numbers is 0 — true. After adding the first number, i=1, the total is the sum of the first 1 number — true. And so on. When the loop ends, i equals the length of the list, so the total is the sum of all numbers. That is the proof.

Think of a delivery driver who must deliver parcels to every house on a street. The driver has a clipboard with a checklist. The invariant is: 'Every house up to the current one has been delivered to.' Before starting, the driver is at the first house — no houses have been passed, so the invariant is true (vacuously). After delivering to house 1, the driver moves to house 2. The checklist shows that houses up to house 1 are done — invariant still true. After each delivery, the driver checks the list: 'Yes, all houses up to this one are done.' The driver continues until the end of the street. At that point, the invariant says 'every house up to the last one is done' — but there are no more houses, so all houses are done. The loop terminates because the street ends. The analogy breaks if the driver skips a house: then the invariant 'every house up to the current one' would be false, but the driver would not notice unless they check. That is why you must check the invariant after every iteration. In programming, the 'checklist' is the invariant statement, and checking it is a mental or code assertion. Also, the invariant does not say anything about what happens after the loop — only that it holds up to the current point. The delivery driver's invariant is not 'all houses are delivered' — that is the goal, not the invariant. The invariant is the stepping-stone that guarantees the goal when the loop ends.

A loop invariant is a condition that is true just before the loop starts, remains true after every iteration of the loop, and is true when the loop terminates, which together prove that the loop accomplishes its stated goal.

Your library notes on this concept say: 'The loop invariant is the specification; the code is only its implementation.' That means the invariant is the plan you wrote down, and the code is just how you carry it out. This connects directly to your notes on Binary Search — the correctness of binary search depends entirely on maintaining an invariant like 'the target, if present, lies between low and high.' Merge Sort relies on an invariant that after each merge, the combined section is sorted. Dynamic Programming uses invariants to ensure that each subproblem's solution is correct before combining them. You also have notes on Big-O Notation, which is about how fast algorithms run — but speed means nothing if the answer is wrong. Loop invariants are how you know the answer is right.