In this tutorial, we’ll explain what’s a loop invariant and how we can use it to prove the correctness of our algorithms.
2. What’s a Loop Invariant For?
A loop invariant is a tool used for proving statements about the properties of our algorithms and programs. Naturally, correctness is the property we’re most interested in. We should be sure that our algorithms always produce correct results before putting them to use.
3. What’s a Loop Invariant and How Do We Prove It?
A loop invariant is a statement about an algorithm’s loop that:
- is true before the first iteration of the loop and
- if it’s true before an iteration, then it remains true before the next iteration.
If we can prove that those two conditions hold for a statement, then it follows that the statement will be true before each iteration of the loop. Furthermore, it follows that the last iteration won’t affect the invariant, so the two conditions ensure that the invariant is true after the loop as well.
As many algorithms do the actual work in the main loop updating their solution iteratively, the invariant we’re after will state a property of the variable(s) holding the solution. Additionally, the invariant should establish a meaningful relationship between the variable(s) and the number of iterations done. That relation should show that the solution contained in the variable(s) after the loop ends is indeed the correct solution the algorithm was supposed to find.
3.1. How to Formulate a Loop Invariant?
Let’s say that we want to sum an array of real numbers:
To be sure that our algorithm works, we should prove that after the loop ends, is equal to the sum of the numbers in :
One way to do so is to formulate a loop invariant about variable :
At the beginning of the -th iteration, is equal to the sum of the first elements of .
How do we check if this is a good invariant? We should verify that the invariant, applied to after the loop, describes the correct solution. In this example, the loop ends when , so the invariant states that at the end of the loop
which is what we want our algorithm to return. So, we identified the invariant we should prove, but, how do we come up with proof?
3.2. How to Prove a Loop Invariant
Proving an invariant is similar to mathematical induction.
The requirement that the invariant hold before the first iteration corresponds to the base case of induction.
The second condition is similar to the inductive step.
But, unlike induction that goes on infinitely, a loop invariant needs to hold only until the loop has ended.
Unfortunately, as each algorithm is unique, there is no universal recipe for writing proofs. All the proofs will have the same structure:
- prove that the invariant holds before the first iteration
- prove that if the invariant holds before an iteration, then it also holds before the next one
but each step in the process will depend on the actual algorithm:
For Algorithm 1, we’d prove the invariant in two steps.
At the beginning of the loop, and . The sum is the sum of no numbers. We can use as its value, so we see that the invariant holds before the first iteration.
Let’s say that the invariant holds at the beginning of the -th iteration:
During the iteration, we add to , so we get
at the end of the iteration. The end of iteration is the same as the beginning of iteration , so the second condition is also fulfilled.
As we’ve shown that
at the end of the loop, proving the invariant also verified that our algorithm was correct.
If the loop is a for–loop, the beginning of an iteration is the point after the loop counter is incremented, but before the loop termination test. That also applies to checking the invariant before the loop.
Let’s now work out two more examples.
4. Sum of Two Binary Numbers
Let’s say that we have two -bit binary numbers: and ( for each ). The result of their addition is an -bit binary number . We can calculate each digit by adding and together with the carryover from :
4.1. Formulate the Loop Invariant
To verify its correctness, we’ll use a loop invariant which states that is the correct result:
At the beginning of the -th iteration, the number is the sum of and .
Would proving this invariant make sure that the returned variable, , really is the correct solution? At the end of the loop, , so per the invariant, the number would be the sum of and . This means that we chose the right invariant for if we prove it, then we’ll also prove that our algorithm is correct.
4.2. Prove the Invariant Holds Before the First Iteration
Before the first iteration of the main loop, and . Since there is no digit , we take to be the solution and the only digit. Similarly, there are no digits and in and so we practically have no numbers to add. We can treat the sum of no numbers as being equal to . So, the invariant is true before the first iteration.
4.3. Prove the Invariant Remains True After Each Iteration
If the invariant holds at the beginning of iteration , does it hold at the beginning of iteration ? Let’s assume that is indeed the sum of and . How do we compute digit ? We sum digits and together with the carryover term from the last iteration in which we computed . When we divide by , the integer remainder is digit and the quotient is the carryover term for the next iteration, which proves that the invariant will be true at the beginning of the next iteration:
5. Insertion Sort
5.1. Define the Loop Invariant
Let’s define the main loop’s invariant:
At the start of each iteration of the for–loop, the subarray consists of the elements originally in on the positions through , but in sorted order.
Is this a good invariant? At the end of the for–loop, , so the invariant will state that the whole is sorted.
5.2. Prove the Invariant Holds Before the First Iteration
We see that before the first iteration. So, the invariant claims that  is a sorted array. It (trivially) holds just as we assumed that zero can be taken as the sum of no numbers.
5.3. Prove the Invariant Remains True After Each Iteration
Let’s suppose that and that we set to at the beginning of an iteration. We need to prove that after the inner while–loop, the elements are greater than (the original ) and that are lower than or equal to .
We can formally prove that by proving the corresponding loop invariant for the while–loop. But, informally, we see that the while–loop moves the elements of one place to the right as long as they’re greater than . When the loop stops, that’s because it found the element () which is lower than or equal to . Therefore, all the elements which were moved to the right, and those are , are greater than . All those unaffected by the while–loop are lower than : . So, when we place at the -th position in , the whole subarray will be sorted.
6. Trivial Statements
In proving that an invariant holds before the first iteration, we usually rely on statements such as:
- The sum of no numbers is equal to zero.
- An array that has only one element is sorted.
Those are the statements we can take to be true without proof. They’re called trivial and are widely used in proving base cases.
In this article, we explained what’s a loop invariant and showed how to prove it. We also worked out a couple of examples to illustrate how we can use a loop invariant to verify an algorithm’s correctness.