Which complexities are too slow

16 June 2026

Two shapes flew off the chart in the first module, so when do O(2ⁿ) and O(n!) actually show up? When you generate every possibility.

Say a customer wants every possible combination of toppings on offer. Each topping is either on or off, that's 2 choices, and with n toppings you get 2 × 2 × ... = 2ⁿ combinations. That's O(2ⁿ), exponential. Or say you want to list every order in which you could serve the n people in the queue: that's n! permutations, O(n!), which is ridiculous.

These are the brute-force "try literally everything" shapes. The whole point of this section is so you can recognise them and stop before you compute. There's almost always a better way in than brute force. The grapher already showed you why you can't just run it: a few dozen items and you're past the lifetime of the universe.

This is the doorstep of NP-hard problems: ones where no known approach does better than that exponential blow-up in the worst case (the travelling salesman's route, packing a van optimally, and similar). You don't need the theory to do the job, just recognise the smell of "try every combination" and know that the answer is often "we approximate" rather than "we solve it exactly".

What lives, what dies

Here's a "what size of n can each shape survive" table:

O(log n) or O(1): basically free. Throw whatever you want at it.
O(n) and O(n log n): comfortably millions. This is the target for most real work.
O(n²): fine into the low thousands, sluggish at a hundred thousand, dead at a million.
O(2ⁿ) and O(n!): a couple of dozen items and it's game over.

With those break points you can look at an approach with an expected data size and know, before writing a line of code, whether it'll cope.