Algorithms and complexity
Big-O as intuition — estimating how cost grows so you know what will scale.
- Estimate how an algorithm's cost grows with input size
- Recognise the common complexity classes in real code
- Decide when a slower, clearer algorithm is the right choice
An algorithm is a precise procedure for solving a problem. Complexity is how its cost grows as the input gets bigger. You don't need heavy maths here — you need an intuition for "will this still be fine when there's a million of them?" That intuition has a name: Big-O notation.
Count work, not seconds
Big-O ignores the exact speed of your machine and asks a more durable question: as the input doubles, how does the work grow? It counts operations in broad strokes, which is what actually predicts behaviour at scale.
The classes you'll actually meet
In rough order from best to worst:
- O(1) — constant. Same cost no matter the size. Looking up a key in a map.
- O(log n) — logarithmic. Cost grows very slowly; doubling the data adds one step. Binary search.
- O(n) — linear. Cost grows in step with size. Visiting every item once.
- O(n log n). The sweet spot for good sorting algorithms.
- O(n²) — quadratic. Cost grows with the square. A loop inside a loop over the same data. Fine for 100 items, painful for 100,000.
- O(2ⁿ) — exponential. Doubling the input doubles the cost again. Avoid for anything but tiny inputs.
The practical headline: a nested loop over the same big collection (O(n²)) is the most common accidental performance trap. Often it's a list membership check that should have been a set (O(1)) — the data-structures lesson in action.
Space matters too
Complexity isn't only about time. An algorithm might be fast but hold the entire dataset in memory (O(n) space). On big inputs, memory can be the limit that bites first. The same "how does it grow?" question applies.
Clarity vs cleverness
Faster is not always better. For a list of ten items, the simplest O(n²) approach may be more readable and perfectly fast — and readability has real value. Optimise complexity where the input can grow large; prefer clarity where it can't. Knowing which case you're in is the skill.
"Premature optimisation is the root of all evil" — but its twin sin is shipping an O(n²) loop into a path that will one day see large input. Use Big-O to tell the difference: optimise what will scale, leave the rest simple.
Where to go next
Theory in hand, we return to practice: reading unfamiliar source code — how to navigate a real system written by others (or by an agent).