FREE LESSON · Algorithms & data structures · 2 OF 14
Big O Notation and Algorithm Correctness
Correctness and cost: Invariants, growth rates, and honest analysis
An algorithm needs two proofs: it gives the right answer, and it finishes within the required resources.
A loop invariant supports correctness; a decreasing measure supports termination. Time and space analysis count how work grows with input size. Worst case gives a bound, amortized analysis spreads rare expensive operations across a sequence, and expected analysis depends on a probability model.
Never quote a complexity class without naming the input measure, operation, and case.
Binary search couples an invariant to logarithmic progress
In a sorted array, the candidate interval contains every location where the target could still be. One comparison removes roughly half of it while preserving that invariant. After k steps at most n/2^k candidates remain, so k grows like log₂n. A boundary convention such as [low, high) keeps empty ranges and updates precise.
The complexity comes from the progress measure; correctness comes from never discarding a valid answer.
Sources and further reading
- Introduction to Algorithms, 6.006: MIT OpenCourseWare
- Open Data Structures: Pat Morin · open textbook