Informal Algorithmic Complexity as a Reading Skill

Two algorithms for the same problem — exhaustive enumeration and bisection search for a square root, back in Exhaustive Enumeration and Approximate Solutions and Bisection Search and the Perils of Floats — can differ by a factor of fifty million in the number of steps they take on the same input. This note gives that observation a name — asymptotic complexity — and a vocabulary for talking about it: Big O notation, and the handful of complexity classes (constant, logarithmic, linear, log-linear, polynomial, exponential) that essentially every algorithm this vault will ever show falls into. This is deliberately a reading skill, not a proof-writing one: docs/programme-profiles/library/introduction-to-python.md's Branch A/B split defers the rigorous derivation of running-time bounds to learn/library/programming/ds-a/'s dedicated complexity topic, and this note's job is only to make you fluent enough to read "$O(n \log n)$" in a library's documentation and understand roughly what it promises.

Learning objectives. By the end of this note you should be able to: