Analyse Sequential and Nested Loops

Loops one after another add their costs, and a loop inside a loop multiplies them.

Loops placed one after another add their counts, and a loop placed inside another multiplies them. This card covers both rules, and a third loop shape whose counter halves, by counting three short Python functions line by line.

The goal is to state each function's Big O class from its code alone. You need the four-step count: name the input size n, find the lines that repeat, count their runs, and keep the largest term. In Python, // divides and rounds down.

Before the steps: how many pairs does a loop inside a loop make from 6 items, and how many halvings take 1,000 down to 1?

36, which is 6 × 6, and 9, because 1,000 halves to 1 in nine steps when each halving rounds down.

Each step below shows a function, then the runs of its lines as a traced run counted them.

Three loop shapes, counted

Two loops in sequence

min_and_max walks the list twice: once for the smallest item, then once for the largest.

min_and_max.pypy

def min_and_max(items: list[int]) -> tuple[int, int]:
    smallest = items[0]
    for item in items:
        smallest = min(smallest, item)
    largest = items[0]
    for item in items:
        largest = max(largest, item)
    return smallest, largest

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

min_and_max([3, 1, 4, 1, 5]) = (1, 5)
min_and_max([7]) = (7, 7)
min_and_max([2, 2]) = (2, 2)

The second loop starts only after the first has finished, so their counts add.

Runs of each line of min_and_max at n = 8, counted by a traced run
Line	Runs	Why
3, first loop's header	9	n + 1: once per item, once more to stop
4, first loop's body	8	n: once per item
6, second loop's header	9	n + 1, after the first loop has ended
7, second loop's body	8	n
2, 5 and 8	1 each	Outside both loops

The bodies run n + n = 2n times, so min_and_max is O(n). Two passes over a list are still linear.

A loop inside a loop

all_pairs builds every ordered pair of items, so its inner loop runs in full for each pass of the outer one.

all_pairs.pypy

def all_pairs(items: list[str]) -> list[tuple[str, str]]:
    pairs = []
    for first in items:
        for second in items:
            pairs.append((first, second))
    return pairs

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

3 items give 9 pairs
6 items give 36 pairs
0 items give 0 pairs

Each line inside the inner loop runs once per inner pass, for each outer pass, so the counts multiply.

Runs of each line of all_pairs at n = 6, counted by a traced run
Line	Runs	Why
3, outer loop's header	7	n + 1
4, inner loop's header	42	n + 1 for each of the n outer passes: 6 × 7
5, inner loop's body	36	n for each of the n outer passes: 6 × 6
2 and 6	1 each	Outside both loops

Line 5 runs n × n = n² times, so all_pairs is O(n²).

A counter that halves

halvings counts how many times n can be halved before it reaches 1. Its loop does not step through items; it shrinks its counter.

halvings.pypy

def halvings(n: int) -> int:
    steps = 0
    while n > 1:
        n = n // 2
        steps += 1
    return steps

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

halvings(1) = 0
halvings(8) = 3
halvings(1000) = 9
halvings(2000) = 10
halvings(1000000) = 19

At n = 1,000 the traced run counted line 3 ten times and lines 4 and 5 nine times each. Nine is log₂ 1,000 rounded down, since 2⁹ = 512 and 2¹⁰ = 1,024. The body runs about log n times, so halvings is O(log n).

Check each class against the doubling test. Doubling n doubles a linear count, so the bodies of min_and_max ran 4 + 4 times at n = 4 and 8 + 8 at n = 8. It quadruples a quadratic one: 3 items give 9 pairs and 6 give 36. It adds one pass to a logarithmic one: 1,000 needs 9 halvings and 2,000 needs 10. Every output above behaves as its class predicts, so the counts are right.

Sequence adds, nesting multiplies, and a counter that halves gives a logarithm, so a loop's class can usually be read from its headers before it runs.

← → move through sections and cards