0
Challenge · 19Cost: Time and Space
The complexity ladder
Complexityused in ~100% of apps
There are only six rungs you will ever need, and they are separated by staggering distances. Knowing where a solution sits on this ladder, and where the next rung down would put it, is most of what optimising means.
Core idea. Six shapes, from unchanging to doubling. The gaps between them are not small increments. Moving down one rung can turn ten billion steps into twenty. Recognising the rung tells you whether your solution can possibly finish.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
steps taken when n = 1,000,000
O(1)arr[i] · map.get · set.has
1
O(log n)binary search
20
O(n)one pass
1,000,000
O(n log n)sorting
20,000,000
O(n²)loop inside a loop
1,000,000,000,000
O(2ⁿ)every combination
beyond counting
A computer manages roughly 100 million simple steps a second. Find that line on the ladder.
↑ play a little first, then dig in