An invariant keeps the plan true.

An invariant is a promise that remains true while an algorithm runs. It gives every step a meaning and helps us explain correctness.

A promise inside a loop

When finding a maximum, the promise can be: best is the largest value we have visited so far. It is true after the first item, and each comparison keeps it true.

• Show the promise is true before the loop.
• Show one loop step keeps it true.
• Use the promise when the loop ends to explain the answer.

Good variable names reveal the invariant

def smallest(numbers):
    smallest_so_far = numbers[0]

    for number in numbers[1:]:
        if number < smallest_so_far:
            smallest_so_far = number

    return smallest_so_far

print(smallest([8, 3, 6, 2, 5]))  # 2

Invariants are especially helpful for two pointers, binary search, sorting, and any loop where indexes move in different ways.

You do not need formal language. A short sentence about what is already known is enough to guide the code.

Your tiny challenge

For a loop that adds numbers, finish this sentence: after visiting the first k items, total equals...