Shows why plausible-looking O(n) 2D divide-and-conquer algorithms can silently fail correctness—and how proving an invariant rescues both correctness and O(n log n) runtime.
Opening lecture of MIT 6.006 analyzing 1D and 2D peak-finding algorithms: greedy ascent pitfalls, divide-and-conquer recurrences T(n) = T(n/2) + Θ(1), and subtle counterexamples when generalizing to grids.
Step 1 of 5 in this path
Dynamic Programming I: Fibonacci, Shortest Paths