Card 03/ 08
Calling Every Pair of Nested Loops O(n²)
An inner loop that runs a fixed number of times, or halves its counter, costs far less.
Nested loops multiply, but they multiply by how many times the inner loop really runs, which is not always n. Calling every loop inside a loop O(n²) is the mistake. This card covers where that reading goes wrong, what it costs, and the count that replaces it.
A function checks each of n orders against a sorted price list with binary search, which halves the range it searches at every step. A reviewer sees a loop inside a loop, calls it O(n²), and asks for a rewrite of code that was never slow.
Before the listing: the outer loop runs n times, and the inner loop halves a counter from n down to 1. At n = 1,000, how many times does the inner body run in all?
9,000: nine halvings for each of the 1,000 outer passes, against the 1,000,000 that O(n²) predicts.
The function has this shape, run at three sizes:
def halving_pairs(n: int) -> int:
work = 0
for _ in range(n):
k = n
while k > 1:
k = k // 2
work += 1
return workn = 8: inner body ran 24 times, against n² = 64
n = 1000: inner body ran 9000 times, against n² = 1000000
n = 2000: inner body ran 20000 times, against n² = 4000000Read by shapemultiplies n by n
Two loops, one inside the other, so n × n: O(n²). At n = 1,000 that predicts 1,000,000 runs of the inner body.
Counted by linemultiplies n by the inner count
The outer loop runs n times. The inner loop halves k from n until it reaches 1, so it runs log₂ n times, rounded down: 9 at n = 1,000. The body runs 1,000 × 9 = 9,000 times: O(n log n).
The run agrees with the count, not the shape: 9,000 runs at n = 1,000. Nesting multiplies the outer count by the inner count, and the inner count is set by the inner loop's own header. Here that header halves its counter, so the inner count is log n. An inner loop that runs a fixed number of times costs less still: three passes inside a loop of n give 3n, which is O(n), and a traced run counted 3,000 inner runs at n = 1,000.
The shape reading overestimated this function by more than a hundred times at n = 1,000, and the gap widens as n grows. It also fails the other way: a reader who judges by shape stops counting, and misses the quadratic work hidden inside a single loop.
Count the inner loop from its own header first, in terms of the variables it uses, and write the product, such as n × log n, before you simplify. Call nested loops O(n²) only when the inner count is itself proportional to n.
← → move through sections and cards