--- title: "Loop Invariants and Proving an Algorithm Correct" description: "A loop invariant is a statement that holds before a loop starts, survives every pass, and gives the wanted result once the loop stops. Stating one turns the claim that code seems to work into an argum" canonical: https://lightmysky.com/learn/computing/loop-invariants-and-proving-an-algorithm-correct-mt_fWnstju2ns source: https://lightmysky.com/learn/computing/loop-invariants-and-proving-an-algorithm-correct-mt_fWnstju2ns.md retrieved: 2026-09-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Loop Invariants and Proving an Algorithm Correct A loop invariant is a statement that holds before a loop starts, survives every pass, and gives the wanted result once the loop stops. Stating one turns the claim that code seems to work into an argument that it works on every input. Subject: Computing · Area: Algorithms & Data Structures · Ages 18 to 19 Page: https://lightmysky.com/learn/computing/loop-invariants-and-proving-an-algorithm-correct-mt_fWnstju2ns ## Ready when they can - State the invariant for an insertion sort and check it at entry, after a pass, and at exit - Use an invariant to argue a summing loop is right for a list of any length - Find the input that breaks a proposed invariant and repair the statement ## Lesson: Proving a loop right on every input A correct algorithm does two things: it gives the right answer for every allowed input, and it stops instead of running forever. Testing builds confidence because it is great at finding mistakes. But testing can never prove you right, since one more untried input always waits, and it might be the one where your code fails. The tool for proof is a loop invariant. It is a statement that is true before the loop starts, stays true after every single pass, and turns into exactly what you want when the loop ends. Picture a rule that holds at the bottom of a ladder and survives every rung: then it must hold at the top too. **Example.** Sort cards by repeatedly selecting the smallest that remains and swapping it into the next spot. After step k, the first k cards are the k smallest, sitting in order: true at the start, kept true by each swap, and the whole hand is sorted at the end. Insertion sort keeps the same style of promise over the cards handled so far, and a summing loop promises that the running total equals the sum of the items seen so far. **Tip.** Always ask what makes a while loop stop. Halving an even number again and again ends for 16, which falls to 8, 4, 2 and then 1, but it never ends for 0, because 0 is even and half of 0 is still 0. Repair the claim by adding that 0 is not allowed. A loop that counts down from 5 prints 5, 4, 3, 2 and 1, then meets 0 and stops on its own. **Recap.** State what holds before, during and after your loop, and the final result follows for every input. ## Practice 10 questions on this page, each with its working shown. ## Needs first - [Tracing a Program by Hand](https://lightmysky.com/learn/computing/tracing-a-program-by-hand-mt__rsnZ5Goow) - [Proof by Induction and Strong Induction](https://lightmysky.com/learn/mathematics/proof-by-induction-and-strong-induction-mt_7lvC02JBOC) - [Quadratic Sorts: Bubble and Insertion](https://lightmysky.com/learn/computing/quadratic-sorts-bubble-and-insertion-mt_cBUIBa15jQ) - [Proof by Deduction and Exhaustion](https://lightmysky.com/learn/mathematics/proof-by-deduction-and-exhaustion-mt_QNWvbkg04f) ## Opens up - [Greedy Choice and the Exchange Argument](https://lightmysky.com/learn/computing/greedy-choice-and-the-exchange-argument-mt_9Fj28VDAV-) - [Asymptotic Notation Made Precise](https://lightmysky.com/learn/computing/asymptotic-notation-made-precise-mt_B0Z6Syy8Ve) - [Randomised Quicksort and Expected Running Time](https://lightmysky.com/learn/computing/randomised-quicksort-and-expected-running-time-mt_fcKF7zfzpX) - [Property-Based Testing](https://lightmysky.com/learn/computing/property-based-testing-mt_QqCNKT06IY)