Big-O: measuring how code scales

Two programs, one answer, very different speeds

Up to now, if a program gave the right answer, it was good enough. That changes the moment the data gets big. Two programs can agree on every answer and still be worlds apart: one finishes instantly on a million items, the other is still running when you go home.

The question this lesson answers is not "how many seconds does it take?" A faster laptop changes the seconds but not the underlying behaviour. The real question is: as the input grows, how does the amount of work grow with it? That shape of growth is what we measure, and Big-O is the notation we write it in.

Counting the work, not the clock

Timing a program with a stopwatch is unreliable. The number depends on your machine, what else it is running, even how warm the processor is. So instead of timing, we count the steps the program takes as a function of the input size, which we call n.

Look at these two loops over a list of n items:

# Loop A: look at each item once
for item in data:
    print(item)

# Loop B: for each item, look at every item again
for a in data:
    for b in data:
        print(a, b)

Loop A does n prints. Loop B does n prints for each of the n items, so n * n = n² prints. On a list of 10 that is 10 versus 100. On a list of 1000 it is 1000 versus 1,000,000. Same idea, wildly different work. The nesting is the tell: a loop inside a loop usually turns n into n².

Big-O: the shape of growth

Big-O keeps only the part that matters as n gets large, and throws away constants and small terms. We do not say "about 3n plus 7 steps"; we say the growth is O(n). Three shapes cover most of what a beginner meets:

• O(1), constant. The work does not grow with n at all. Reading data[0] or len(data) takes the same time whether the list has ten items or ten million.
• O(n), linear. The work grows in step with n. One pass over the data, like Loop A. Double the data, double the work.
• O(n²), quadratic. The work grows with the square of n. A loop inside a loop, like Loop B. Double the data, four times the work.

A worked example: are there any duplicates?

Say you have a list of student ID numbers and you want to know if any ID appears twice. Here is the natural first attempt: compare every item with every item after it.

def has_duplicate_slow(ids):
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            if ids[i] == ids[j]:
                return True
    return False

It works, but it is a loop inside a loop, so it is O(n²). On a class of 30 that is nothing. On a national database of a million IDs it is a trillion comparisons, and you will wait a very long time.

Now use a tool you already met, a set, which can check membership almost instantly:

def has_duplicate_fast(ids):
    seen = set()
    for one in ids:
        if one in seen:
            return True
        seen.add(one)
    return False

This makes a single pass over the list, and each in check on a set is roughly O(1), so the whole function is O(n). Same answer as the slow version, but on a million IDs it finishes in the blink of an eye. The lesson is not "sets are magic"; it is that choosing the right data structure changed the shape of the growth, from n² down to n.

That trade has a cost worth naming: the fast version keeps a seen set, so it uses more memory to save time. Big-O describes memory growth too, and swapping time for space is one of the most common decisions you will make as a programmer.

Drag the slider to watch the two duplicate-checkers pull apart: the nested-loop version climbs as n² while the set version rises only with n.

Check yourself

1. Why do we measure the growth of work as n increases, rather than just timing the program in seconds on our own computer?
2. A function has a single for loop over a list of n items, and no loop inside it. What is its Big-O, and what happens to the work when the list doubles in size?
3. The fast duplicate check is O(n) but uses extra memory for the seen set, while the slow one is O(n²) but uses almost none. Describe a situation where you might still reach for the slower version.