ExampleDifficulty: Intermediate2 min

Complexity Example: Comparing Two Lists of Different Lengths

Two independent inputs keep two variables, so the cost is O(n · m), not O(n²).

When a function takes two inputs whose sizes can vary separately, its cost needs a variable for each. This card covers one function written two ways, each finding which of n guests who arrived were among m invited names, and counts both.

The first version compares every guest with every invited name:

common_names_nested.pypy

def common_names(guests: list[str], invited: list[str]) -> list[str]:
    common = []
    for guest in guests:
        for name in invited:
            if guest == name:
                common.append(guest)
    return common

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

[Cai, Fay]
[]

A traced run counted its lines with 1,000 guests and 10 invited names.

Before the table: with 1,000 guests and 10 invited names, how many comparisons does the nested version make?

10,000: ten for each of the 1,000 guests.

The table gives the runs of each line in the loops.

Runs of the nested version at n = 1,000 and m = 10, counted by a traced run
Line	Runs	Why
3, outer loop's header	1,001	n + 1
4, inner loop's header	11,000	m + 1 for each of the n guests
5, the comparison	10,000	m for each of the n guests: n · m

The second version puts the invited names in a set first, so each guest needs one lookup:

common_names_set.pypy

def common_names(guests: list[str], invited: list[str]) -> list[str]:
    invited_set = set(invited)
    common = []
    for guest in guests:
        if guest in invited_set:
            common.append(guest)
    return common

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

[Cai, Fay]
[]

The same run counted it at the same sizes.

Runs of the set version at n = 1,000 and m = 10, counted by a traced run
Line	Runs	Why
2, building the set	1	Runs once, but copies all m names: O(m)
4, the loop's header	1,001	n + 1
5, the lookup	1,000	n lookups, each O(1) expected

The nested version made 10,000 comparisons, not the 1,000,000 that calling it O(n²) predicts. Nothing ties the two sizes together, so neither variable can stand in for the other: the nested version is O(n · m) and the set version O(n + m) expected.

The same structure holds wherever two inputs grow separately. Loops over different inputs multiply as n · m when nested and add as n + m in sequence. The count becomes n² or 2n only when both loops run over the same input.

← → move through sections and cards