Reasoning about complexity before optimising

Goal

Spot code whose cost grows faster than its input in review, and choose data structures whose documented complexity matches the access pattern.

Prerequisites

Knowledge of the container operations' costs in the language used (Python's wiki lists them: list append amortised O(1), x in list O(n), dict and set membership average O(1)).

Steps

1. For every loop, ask what the body costs: a membership test on a list inside a loop over another list is O(n·m); convert the inner list to a set.
2. Look for repeated work: recomputing a sum or re-sorting inside a loop; hoist it or maintain it incrementally.
3. Check string building: repeated += in a loop may be quadratic; collect parts and join once.
4. Bound recursion and queues; unbounded growth with input is a denial-of-service path.
5. Estimate with realistic sizes: n = 10⁵ makes O(n²) ≈ 10¹⁰ operations, which is minutes, not milliseconds.
6. Confirm with a profile only where the estimate is unclear or the constant factors matter.

Expected result

Reviews catch the quadratic path before it reaches production; data structures are chosen for the operations actually performed.

Limits and test basis

Big-O hides constants and cache effects; a linear scan of a small list beats a hash lookup. Amortised bounds can have expensive individual operations. The cost table follows the cited wiki page; the method is general practice.