PYTHON / LOOPS
Nested loops and their cost
Predict how much work a nested loop really does by multiplying its iteration counts, and cut that work with hoisting or lookup tables.
What you will learn
- Compute total inner-body runs as the product of the loop iteration counts
- Recognise n(n-1)/2 triangular loops as still quadratic, just half as many steps
- Move loop-invariant work out of the inner loop to shrink the constant factor
- Replace an inner list scan with a set or dict lookup to drop from n*m to n+m
Understanding Nested loops and their cost
A nested loop runs its inner body once for every combination of outer and inner iterations, so the count multiplies rather than adds. An outer loop of 1000 items wrapping an inner loop of 1000 items executes the body a million times, and adding one more level of nesting over the same data makes it a billion. The number to reason about is never the indentation depth but the product of the iteration counts, so a loop over 100000 rows containing a loop over 3 columns is only 300000 steps and behaves linearly.
The common comparison pattern, where the inner range starts at i + 1 so each pair is visited once, runs n(n-1)/2 times. That halves the step count but does not change the growth: doubling n still roughly quadruples the work, because the dominant term is n squared. This is why quadratic code looks instant on 100 test items and appears to hang on 100000 real ones: 10000 steps versus 5 billion.
Two separate things drive the total time: how many times the body runs, and how expensive one run is. You reduce the first by changing the algorithm, typically by precomputing a set or dict so the inner scan becomes a single hash lookup. You reduce the second by hoisting anything that does not depend on the inner variable above the inner loop, since a call placed inside runs n*m times while the same call placed just outside runs only n times.
def full_grid(n):
steps = 0
for i in range(n):
for j in range(n):
steps += 1
return steps
def upper_pairs(n):
steps = 0
for i in range(n):
for j in range(i + 1, n):
steps += 1
return steps
print("n", "full", "pairs")
for n in (4, 40, 400):
print(n, full_grid(n), upper_pairs(n))The cost of nested loops is the product of their iteration counts, not the number of loops you wrote.
Worked examples
An inner scan replaced by a set lookup
Counts the actual comparisons done by a nested search versus a hash lookup on the same data.
orders = ["a1", "b2", "c3", "d4"]
shipped = ["b2", "d4"]
scans = 0
pending = []
for o in orders:
found = False
for s in shipped:
scans += 1
if o == s:
found = True
break
if not found:
pending.append(o)
print(pending, scans)
shipped_set = set(shipped)
lookups = 0
pending2 = []
for o in orders:
lookups += 1
if o not in shipped_set:
pending2.append(o)
print(pending2, lookups)Example explained
Line 1scans += 1 sits in the inner loop, so it counts one string comparison per candidate pair.
Line 2The 7 comes from 2 + 1 + 2 + 2: misses cost the full inner pass, hits stop early.
Line 3set(shipped) is built once before the outer loop, so its cost is paid a single time.
Line 4The second version does 4 lookups, one per order, so work grows with len(orders) + len(shipped) instead of their product.
Nesting over a grid is linear in cells
Shows that iterating a nested data structure costs the number of elements, whether you nest loops or flatten them.
grid = [[1, 2, 3], [4, 5, 6]]
visits = 0
total = 0
for row in grid:
for value in row:
visits += 1
total += value
print("nested", total, visits)
flat_visits = 0
total2 = 0
for value in (v for row in grid for v in row):
flat_visits += 1
total2 += value
print("flat", total2, flat_visits)Example explained
Line 1The outer loop runs 2 times and each inner loop runs 3 times, giving 6 body runs, which equals the cell count.
Line 2The generator expression visits exactly the same 6 values, so flattening changes readability, not cost.
Line 3Cost here is proportional to the data size, so two levels of nesting are not automatically quadratic.
Line 4It only becomes quadratic when both loops range over the same n independent items.
Hoisting work out of the inner loop
Counts how many times a helper is called when it is inside the inner loop versus above it.
calls = 0
def normalize(s):
global calls
calls += 1
return s.strip().upper()
titles = [" mr ", " dr "]
names = ["ann", "bob", "cal"]
for t in titles:
for n in names:
label = normalize(t) + " " + n
print("inner:", calls)
calls = 0
for t in titles:
fixed = normalize(t)
for n in names:
label = fixed + " " + n
print("hoisted:", calls)Example explained
Line 1normalize(t) does not depend on n, yet placing it in the inner body runs it 2 * 3 times.
Line 2Moving it between the two for statements runs it once per outer iteration, so 2 times.
Line 3The number of body runs is unchanged; only the per-run cost dropped.
Line 4This is a constant-factor win, so it speeds up quadratic code without changing its growth.
Important notes
Slicing, sorting, in on a list, and str concatenation inside an inner loop each add their own hidden pass, so the real cost can be n squared times m.
Quadratic is not automatically wrong: when the inner range is capped at a small constant, or n is a handful of config entries, the simpler nested loop is the better code.
Common mistakes
Reusing the same variable name in both loops, as in for i in range(n) nested inside for i in range(m): the inner loop overwrites i, so the body indexes the wrong element and no error is raised.
Expecting break in the inner loop to leave both loops; it only ends the inner one, so the outer loop keeps restarting the search and the work stays quadratic.
Writing if item in other_list inside a loop over items: this is a hidden inner loop, so the code passes on a 100-item sample and stalls on a 100000-item file.
Try it yourself
Change, predict, then run
Write count_pairs(items) that uses a nested loop with range(i + 1, len(items)) to count equal pairs while incrementing a comparison counter, then print the counter for a list of 5 and a list of 10 items and check that the second is close to four times the first. Then rewrite it with a dict of value counts and print how many steps that version takes.
Open the Python workspaceCheck your understanding
A loop over 1000 records contains an inner loop over a fixed list of 3 status flags. If the record count doubles to 2000, how does the number of inner-body executions change?
- It doubles, because the inner loop count is a constant that does not grow with the records
- It quadruples, because any two nested loops grow quadratically
- It stays the same, because the inner loop always runs exactly 3 times
- It grows by a factor of 3, matching the number of status flags
Show answer
Total body runs are the product of the counts: 1000 * 3 becomes 2000 * 3, so the work doubles and the growth is linear in records. Quadrupling would only happen if both loops ranged over the same growing collection; nesting alone does not make code quadratic, and the total clearly changes, so 'stays the same' confuses the inner loop's own count with the total.