AntInLoop

Mathematical Proof Techniques for Algorithms

Core proof techniques for verifying algorithm correctness—including Loop Invariants, Mathematical Induction, Exchange Arguments for greedy algorithms, and Proof by Contradiction.

Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code

Mathematical Proof Techniques for Algorithms

Knowing why an algorithm works prevents subtle edge-case bugs and separates guessing from engineering. Four proof techniques cover 95% of algorithm correctness proofs:

| Proof Technique | Best For | Classic Example |

| :--- | :--- | :--- |

| Loop Invariant | Iterative loops (sorting, binary search, two pointers) | Prove arr[0..i] is sorted before/after every pass of Insertion Sort |

| Mathematical Induction | Recursive & DP algorithms | Prove $T(n)$ bounds, tree properties ($E = V - 1$), Merge Sort |

| Exchange Argument | Greedy Algorithms | Swap the first differing choice in an optimal solution with the greedy choice without worsening the objective |

| Proof by Contradiction | Graph optimality & impossibility bounds | Cut property of Kruskal/Prim, Dijkstra correctness |

---

Verifying a Loop Invariant in Code (assert)

Embedding invariants directly as assertions during testing catches off-by-one bugs immediately!

<details>

<summary>Show C++ Example (Binary Search Invariant Check)</summary>

#include <cassert>
#include <iostream>
#include <vector>

int lowerBoundVerified(const std::vector<int>& a, int target) {
    int n = static_cast<int>(a.size()), lo = 0, hi = n;
    // Invariant: for all i < lo, a[i] < target; for all i >= hi, a[i] >= target
    while (lo < hi) {
        assert(lo == 0 || a[lo - 1] < target);
        assert(hi == n || a[hi] >= target);
        int mid = lo + (hi - lo) / 2;
        if (a[mid] >= target) hi = mid;
        else lo = mid + 1;
    }
    assert(lo == hi);
    return lo;
}

int main() {
    std::cout << lowerBoundVerified({1, 3, 5, 7, 9}, 6) << "\n"; // 3
    return 0;
}

</details>

---

Related Algorithms