What Is a Loop Invariant in a Search for the Largest Number?

Blog › Computer Science Explained

· by Julia Berens · 4 min read

An angled close-up of a computer screen filled with rows of glowing green and teal numbers on a dark background.

If you have ever asked, “What is a loop invariant?” start with a list of numbers and a variable called best. As a loop reads the list, the value of best can change. But one fact stays true: best is the largest number among the entries the algorithm has already examined. That fact connects a single comparison inside the loop to the answer the function returns.

What Is a Loop Invariant in This Example?

A loop invariant is a statement that is true before the first iteration and remains true after each iteration. It does not say that the variables stay the same. It says that a relationship between them, or between the variables and the input, continues to hold at those points. The statement may not be true halfway through the loop body, when one variable has been updated but another has not.

Suppose numbers is a nonempty list of integers. We can take its first entry as our starting value and compare each remaining entry with best:

def largest(numbers):
    best = numbers[0]
    i = 1
    while i < len(numbers):
        if numbers[i] > best:
            best = numbers[i]
        i += 1
    return best

Python counts list indexes from zero. Here, i is both the number of entries already examined and the index of the next entry, if there is one. The invariant is: best is the largest of the first i entries. Those entries start at index zero and end just before index i. The word “first” gives the claim a precise boundary.

Watch the Value Change While the Statement Holds

Try the list [-6, -2, -9, -2, -1]. Before the loop starts, the algorithm has examined only -6. The table shows the state after setup and after each complete pass through the loop body, including the increment of i.

Most recent entry examinedEntries examined so faribest
-6 (setup)[-6]1-6
-2[-6, -2]2-2
-9[-6, -2, -9]3-2
-2[-6, -2, -9, -2]4-2
-1[-6, -2, -9, -2, -1]5-1

When the loop sees -9, it keeps -2 because -9 is smaller. When it sees -2 again, it still keeps the old value: tying the largest number does not change what that number is. Notice that best is not the largest number in the whole list until the final pass. The invariant only makes a claim about the part the algorithm has seen.

Prove the Result in Three Steps

Initialization

Before the first loop test, i is 1 and best is numbers[0]. The largest of the first one entry is that entry itself, so the invariant holds. Starting with an actual entry matters. If you started best at zero instead, zero could survive every comparison in a list of negative integers and be returned even though it never appeared in the input.

Maintenance

Assume the invariant holds at the start of a pass. The first i entries already have a known maximum, best. The loop now examines exactly one new entry, numbers[i]. If the new entry is larger than best, it is larger than every entry seen before, so the assignment makes it the new maximum. If it is smaller or equal, the old best is still the maximum.

Either way, best is now the largest among the old entries and the new one. Then i += 1 increases the count to include that new entry. The statement about the first i entries is true again with the updated count. This reasoning does not depend on the numbers in the table. It covers every pass, whether the assignment happens or not.

Termination

Let n be the length of the list. The counter starts at 1, increases by exactly one each pass, and stops when it reaches n. It cannot skip over n. At that point, the invariant says that best is the largest of the first n entries. Those entries are the entire list, so returning best gives the right answer. For a one-entry list, the loop body never runs. Initialization has already established the statement we need at the exit.

Make the Invariant Precise Enough to Use

“best is a number we have seen” is true, but too weak. It would also be true of a broken version that never updates best. Once that version reaches the end, knowing that its answer came from the list does not tell you it found the largest entry. On the other hand, “best is the largest entry in the entire list” is too strong: it can fail before the loop starts. A useful invariant needs to survive each pass and give you enough information to prove the result when the loop stops.

One way to practice is to change the task: return the index of the first occurrence of the largest number. In the new invariant, say that the saved index points to the first occurrence of the maximum among the first i entries. Now the comparison matters in a different way. Updating only for a strictly larger value keeps the earlier index on a tie. Updating for a larger or equal value replaces it with a later index. Try writing the maintenance step for both versions before running either one.

For more ways to practice explaining why code works, see the ICSC training and practice problems or browse Computer Science Explained.

Frequently asked questions

Can an invariant be true if a variable changes?
Yes. The value of best can change while the statement that it is the largest of the entries examined so far stays true.

Does this code work with an empty list?
No. An empty list has no largest entry, and the code tries to read index zero before the loop begins.

Does an invariant prove the loop will stop?
Not by itself. Here, the loop stops because the counter increases by one each pass until it reaches the list length.

About the International Computer Science Competition: an online computer science competition for high school students from around the world. How the rounds work

Written by Julia Berens, Social Media Assistant of the ICSC team.

More articles

All articles