FREE LESSON · Algorithms & data structures · 2 OF 4
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
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.