Complexity Theory (when problems are hard)

Three cliffs, drawn side by side: a cost that calls smaller copies of itself, a cost that’s cheap almost every time and expensive once in a while, and a cliff nobody has ever found a way around.

Before you start. You already know how to read a cost off a line of code - count the loops, and see whether doubling the input doubles the work (Complexity & Big-O). This lesson is the three cases where that trick alone isn’t enough: a job that calls smaller copies of itself, a job that’s fast almost every time and slow once in a while, and a job nobody has ever managed to speed up at all.

The idea in 30 seconds

Reading a cost off code isn’t enough for a job that calls smaller copies of itself, a job that’s cheap almost every time, or a job nobody has ever sped up.
A job that splits into copies of itself has a true cost you get by comparing the work each level does against how many levels there are; the shortcut for that comparison is the master theorem.
A cost that’s occasionally huge can still be cheap on average, if all the cheap moves around it are paying it forward - that’s amortized cost.
P is “solvable fast”; NP is “checkable fast, even if finding one is unknown”; every P problem is also NP.
NP-complete problems are the hardest in NP, all secretly the same problem - crack one fast and you crack every one of them, which nobody ever has.
Nobody has proven finding must be as slow as it looks, but nobody has ever found a fast way to do it either, in fifty-plus years of trying.

Read the story · Skip to the numbers