Counting steps
A stopwatch gives different times on different computers. So we count steps instead: simple actions, like looking at one item. Big O asks how that count grows as n, the number of items, grows from 10 to a million.
Five growth rates
items[5] jumps straight to position 5 in the list. That is 1 step whether the list holds 10 items or a million, so the bar never grows. Big O calls this O(1), constant time.
bisect searches a sorted list by halving it: check the middle, keep the half that can hold x, repeat. A million items need only about 20 halvings, because 2 to the power 20 is about a million.
x in items checks the items one by one. If x is not there, it checks all of them: 10 steps for 10 items, a million for a million. Steps grow at the same rate as n: O(n), linear time.
sorted(items) puts the list in order. Good sorting methods, including Python's, take about n × log n steps: for a million items, a million times about 20, so roughly 20 million steps.
Pairing every item with every item needs a loop inside a loop: n times n steps. 10 items give 100 steps; a million items give a million million, which is a trillion. That is O(n²), quadratic time.
At a million items: 1 step, about 20, a million, about 20 million, and a trillion. If each step took a billionth of a second, the trillion would take about 17 minutes; the 20 million, a fiftieth of a second.
The rules
A loop that runs twice, plus 3 setup steps, costs 2n + 3. At a million that is 2,000,003: the 3 vanishes. The 2 does not change how the count grows, so Big O drops it too: O(n). Likewise, n² + n is O(n²).
x in items is lucky if x comes first: 1 step. If x is somewhere at random, it checks about half the list on average: 500,000. If x is last or missing, all 1,000,000. Big O usually means the worst case.
In practice
You have met lists and dicts. ages["Sam"] finds a key in about 1 step on average, O(1), however big the dict is. items.insert(0, x) must shift every item one place to make room: n steps, O(n).
Big O also measures memory. items[5] needs no extra memory: O(1) space. sorted(items) builds a brand-new list holding all n items, so it needs O(n) extra space. Fast code sometimes trades memory for speed.
Try it in the Python prompt
;; step 1/11 · Count steps, not seconds >>> steps = 0 >>> for x in range(1_000): ... steps += 1 # one step per item ... >>> steps 1000
The bars stand against a log scale: each line on the back wall is 10 times the one below it. On an ordinary scale the trillion bar would be a million times taller than the million bar. The O(log n) bar counts the most halvings binary search can need on n items, which is log₂(n + 1) rounded up: 4 for 10 items, 10 for 1,000 and 20 for 1,000,000. bisect comes from the standard library: from bisect import bisect.