Induction & Recursion · step 11 of 13

Loop invariants & algorithm correctness

A loop invariant is a statement true before the loop starts and preserved by every iteration. Proving one has three named parts: initialisation (it holds initially), maintenance (each iteration preserves it), and termination (combined with the exit condition, it gives the desired result). It is induction on the iteration count, dressed for computer science.

Practise loop invariants & algorithm correctness free → All Induction & Recursion subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

State the invariant preciselyIt must mention the loop variable and describe the partial result achieved so far.
InitialisationShow the invariant holds just before the first iteration — often vacuously, with an empty processed portion.
MaintenanceAssume the invariant before an iteration and prove it holds after. This is the induction step.
TerminationCombine the invariant with the negated loop condition to derive the postcondition.

Worked example

Give and verify a loop invariant for computing a factorial with f = 1 and a loop over i = 1..n doing f = f · i.

Invariant: before the iteration with counter i, f = (i−1)!.
Initialisation: before i = 1, f = 1 = 0! ✓.
Maintenance: assume f = (i−1)!. The body sets f = (i−1)!·i = i!, which is the invariant for i+1 ✓.
Termination: the loop exits after i = n, so f = n!.

Answer. The invariant f = (i−1)! holds throughout, and on exit gives f = n! — the algorithm is correct.

Where marks get dropped

These are the specific errors that cost credit on loop invariants & algorithm correctness questions — QED's rubric penalises each of them separately.

Stating an invariant too weak to give the postcondition at termination. It must be strong enough to finish the job.
Stating one so strong it is not actually preserved. Check maintenance concretely on the loop body.
Omitting the termination argument. Invariance alone does not prove the loop ever ends or produces the answer.

Practise this until it is automatic

Unlimited fresh questions

QED generates new loop invariants & algorithm correctness problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Induction & Recursion mastery is tracked so you know when this is exam-ready.

Loop invariants & algorithm correctness — frequently asked questions

Why is this induction?

Maintenance is exactly the induction step over the number of completed iterations, and initialisation is the base case. Termination extracts the conclusion.

What is the difference between partial and total correctness?

Partial correctness says: IF the loop terminates, the answer is right. Total correctness adds a termination proof, usually via a decreasing measure.

How do I find a good invariant?

Ask what the loop has achieved after k iterations, and write it in terms of the loop variable. Running the loop by hand for two iterations usually reveals it.

The rest of Induction & Recursion

Mathematical, strong & structural induction; recursion. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make loop invariants & algorithm correctness exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →