Counting the Work a Function Does

Count how often each line runs as a function of the input, then keep the largest term.

Analysing a function's time complexity means counting how many times each of its lines runs, written in terms of the input's size, and then simplifying that count with Big O. This card covers the four steps of that count, applied to a function that adds up a list.

A report adds up a day's sales. Today it reads 4,000 of them; next year it may read 400,000. Before anyone times it, you can say how its work will grow by reading its code:

sum_list.pypy

def sum_list(items: list[int]) -> int:
    total = 0
    for item in items:
        total += item
    return total

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

sum_list([3, 1, 4, 1]) = 9
sum_list([7]) = 7
sum_list([]) = 0

Before the steps: on a list of n items, how many times does the loop's header run, and how many times its body?

The header runs n + 1 times, once per item and once more to find the list finished. The body runs n times.

The four steps below make that count for every line.

The four steps, applied to sum_list

Name the input size

Call the number of items in items n. Every count is written in terms of n, so the answer holds for a list of any length.

Find the lines that repeat

Lines 2 and 5 sit outside the loop, so each runs once per call. Lines 3 and 4 belong to the loop, so how often they run depends on n.

Count each line's runs

Line 4, the loop's body, runs once per item. Line 3, the loop's header, runs once per item and once more to find the list finished. A run that counted every line agreed:

How often each line of sum_list ran, counted by a traced run
Line	Runs at n = 4	Runs at n = 8	Runs for n items
2	1	1	1
3	5	9	n + 1
4	4	8	n
5	1	1	1

Simplify with Big O

The total is 1 + (n + 1) + n + 1 = 2n + 3. Keep the fastest-growing term, 2n, drop its constant factor, and sum_list is O(n): doubling the list doubles the work.

So for any function: name the input size, find the lines inside loops or recursive calls, count each line's runs in terms of that size, and keep the largest term. The line that runs most often decides the class, so in practice you can find the deepest repeating line and count only that.

Counting is not timing, and a line is not always one step. A run counts as one step only when that line's own work does not grow with n. A line that calls another function, including a built-in such as sorted, costs whatever that call does.

Every cost this subject gives for a data structure comes from this count. Being able to repeat it lets you check a claimed cost against the code instead of trusting it.

← → move through sections and cards