Loop invariants

A loop invariant holds before every iteration. Initialization, maintenance and termination turn it into a correctness proof.

Remember: Initialize → maintain → conclude.

Example: Before i=2 in [3,-2,5], sum=1 is exactly the sum of the first two values.

Time: O(n). Auxiliary space: O(1).

Formula: Before iteration i: sum = Σ a[k], for 0 ≤ k < i

Up to 15 integers, including an empty sequence. Initialization, maintenance, termination: prove that prefix summation returns the total. A loop invariant is a statement preserved by every iteration.

Complexities describe the underlying algorithm; tutorial snapshots and rendering can use additional resources.

The interactive workspace loads here when JavaScript is available. You can still browse the learning notes and links above without it.