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.
Playground, this isn't a screenshot
steps taken when n = 1,000,000
O(1)
1
O(log n)
20
O(n)
1,000,000
O(n log n)
20,000,000
O(n²)
1,000,000,000,000
O(2ⁿ)
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