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>
---