Mathematics.

algorithm analysis

Algorithm Correctness Proofs

Theory of Computation35 minDifficulty5 out of 10

You should know: mathematical induction

Overview

Proving an algorithm correct means showing it produces the right output for every valid input, not just the test cases you happened to check. The two workhorse techniques are loop invariants (for iterative algorithms) and induction (for recursive algorithms) — both are really the same idea in different clothes: establish a property that starts true, stays true through each step, and implies correctness once the process finishes.

Intuition

A loop invariant is a statement that's true before the loop starts, stays true after every iteration, and — combined with the fact that the loop eventually stops — implies the loop did what you wanted. It's exactly mathematical induction applied to a running program: the invariant is your 'induction hypothesis', and each loop iteration is an 'inductive step'.

Formal Definition

Definition

A loop invariant proof has three parts:

Initialization: the invariant holds before the first iteration\textbf{Initialization: } \text{the invariant holds before the first iteration}
Maintenance: if the invariant holds before an iteration, it still holds after\textbf{Maintenance: } \text{if the invariant holds before an iteration, it still holds after}
Termination: when the loop ends, the invariant (+ the loop’s exit condition) implies correctness\textbf{Termination: } \text{when the loop ends, the invariant (+ the loop's exit condition) implies correctness}

Derivation

Proving correctness of a loop that finds the maximum of an array a[0..n-1]:

Invariant: after processing a[0..i−1], m=max⁡(a[0],…,a[i−1])\text{Invariant: after processing } a[0..i-1], \ m = \max(a[0], \ldots, a[i-1])
Initialization: i=1,m=a[0]=max⁡(a[0..0]). True.\text{Initialization: } i=1, m=a[0]=\max(a[0..0]). \text{ True.}
Maintenance: if m=max⁡(a[0..i−1]), setting m←max⁡(m,a[i]) gives m=max⁡(a[0..i]).\text{Maintenance: if } m=\max(a[0..i-1]), \text{ setting } m \leftarrow \max(m, a[i]) \text{ gives } m=\max(a[0..i]).
Termination: at i=n, m=max⁡(a[0..n−1]), the whole array, correct.\text{Termination: at } i=n, \ m = \max(a[0..n-1]), \text{ the whole array, correct.}

Properties

Recursive correctness via induction

Base case: correct on smallest input. Inductive step: assuming correctness on smaller subproblems, the recursive combination is correct.\text{Base case: correct on smallest input. Inductive step: assuming correctness on smaller subproblems, the recursive combination is correct.}

Applications

Formal verification tools (used in safety-critical software like avionics or medical devices) mechanize loop-invariant and inductive proofs to certify code correctness.

Worked Examples

  1. Base case: interval of size 0 correctly reports 'not found'.

    n=0⇒not found (vacuously correct)n=0 \Rightarrow \text{not found (vacuously correct)}

  2. Inductive step: assume binary search is correct on any interval smaller than n. On an interval of size n, comparing to the midpoint either finds the target or recurses into a strictly smaller interval, which is correct by the inductive hypothesis.

    target=a[mid] or recurse on left/right half (size<n)\text{target} = a[\text{mid}] \ \text{or recurse on left/right half (size} < n)

Answer: Correct by strong induction on interval size.

Practice Problems

Difficulty 5/10

State the loop invariant that proves insertion sort correctly sorts an array.

Difficulty 4/10

A loop computes s = 0; for i = 1..n: s = s + i. Give a loop invariant that proves it returns n(n+1)/2, and verify the three invariant steps.

Difficulty 6/10

What loop invariant proves binary search is correct, and why does it guarantee termination?

Difficulty 4/10

Your sorting function passes 10,000 random test cases. What does this establish about its correctness?

Common Mistakes

Common Mistake

Testing an algorithm on several examples counts as a proof of correctness.

Passing test cases only shows the algorithm works on THOSE inputs. A correctness proof must hold for every valid input, including edge cases (empty input, all-equal elements, maximum size) that testing might miss.

Common Mistake

Forgetting to separately prove termination (that the loop/recursion actually ends).

A loop invariant alone only shows PARTIAL correctness (if it ends, the answer is right) — you must also argue TERMINATION (e.g. a strictly decreasing, bounded-below quantity) for TOTAL correctness.

Quiz

A loop invariant proves correctness through three steps. They are:
Passing many test cases, versus a correctness proof:
For binary search, why does the loop invariant also give the O(log n) running time?

Summary

  • Correctness proofs show an algorithm is right for ALL valid inputs, not just tested cases.
  • Loop invariants: a property true at initialization, maintained by each iteration, and useful at termination.
  • Recursive algorithms are proved correct by induction: base case + inductive step assuming smaller subproblems are correct.
  • Full correctness requires proving BOTH partial correctness (right answer if it halts) and termination (it does halt).

References

  1. WebsiteWikipedia — Correctness (computer science)