Data Structures: Big-O in Practice and Choosing by Operation

A festival check-in desk issued 2,000 wristbands and scans each one at the gate. The first prototype stored issued wristbands in a list and asked "is this one valid?" with a plain in. It felt instant during testing with 50 wristbands and crawled on opening day. Nothing was wrong with the logic; the program was simply doing far more work per scan than anyone realised. Big-O is the vocabulary for talking about that work, and choosing a data structure is mostly choosing which operations will be cheap.

Count the work, not the seconds

Stopwatch timings depend on your laptop, Python version and what else is running. Counting is more honest. The class below counts every time Python has to compare two wristbands for equality, so you can see exactly how many comparisons a membership test costs.

class Wristband:
    scans = 0

    def __init__(self, code):
        self.code = code

    def __eq__(self, other):
        Wristband.scans += 1
        return self.code == other.code

    def __hash__(self):
        return hash(self.code)


issued = [Wristband(f"W{n:04d}") for n in range(2000)]

# Linear search: list membership
Wristband.scans = 0
probe = Wristband("W1999")
print("in list ->", probe in issued, "| equality checks:", Wristband.scans)

Wristband.scans = 0
print("missing  ->", Wristband("W9999") in issued, "| equality checks:", Wristband.scans)

# Hash lookup: set membership
gate = set(issued)
Wristband.scans = 0
print("in set   ->", probe in gate, "| equality checks:", Wristband.scans)
Wristband.scans = 0
print("missing  ->", Wristband("W9999") in gate, "| equality checks:", Wristband.scans)

in list -> True | equality checks: 2000
missing  -> False | equality checks: 2000
in set   -> True | equality checks: 1
missing  -> False | equality checks: 0

The list had to walk past every earlier wristband to find the last one, and for a missing wristband it checked all 2,000. The set jumped almost straight to the right spot. Double the wristbands and the list work doubles; the set work does not change. Those two behaviours are called O(n) (linear) and O(1) (constant, on average). The set's single equality check is the confirmation that the item found in the bucket really is the one you asked for.

Reading Big-O without the maths

Big-O describes how the amount of work grows as the input size n grows, ignoring constant factors. It is a growth rate, not a speed. The table shows what the common rates look like at two sizes.

The last column is where the wins are. A quadratic algorithm at a million items is a trillion steps; nobody waits for that. A linear one at the same size finishes comfortably. Most performance fixes in everyday code are moving from the bottom row of the table up one or two rows.

The accidental quadratic

Here is the pattern that bites people most often: finding repeated scans by comparing every pair, versus remembering what you have already seen. Both functions return the same answer, and the counters show the price.

def duplicate_scans_pairs(scans):
    comparisons = 0
    dupes = []
    for i in range(len(scans)):
        for j in range(i + 1, len(scans)):
            comparisons += 1
            if scans[i] == scans[j] and scans[i] not in dupes:
                dupes.append(scans[i])
    return dupes, comparisons


def duplicate_scans_set(scans):
    seen, dupes, lookups = set(), [], 0
    for code in scans:
        lookups += 1
        if code in seen:
            if code not in dupes:
                dupes.append(code)
        else:
            seen.add(code)
    return dupes, lookups


for n in (100, 400, 1600):
    scans = [f"W{i % (n - 5):04d}" for i in range(n)]
    d1, c1 = duplicate_scans_pairs(scans)
    d2, c2 = duplicate_scans_set(scans)
    assert d1 == d2
    print(f"n={n:5d}  pairwise comparisons={c1:8d}  set lookups={c2:5d}  dupes={len(d1)}")

n=  100  pairwise comparisons=    4950  set lookups=  100  dupes=5
n=  400  pairwise comparisons=   79800  set lookups=  400  dupes=5
n= 1600  pairwise comparisons= 1279200  set lookups= 1600  dupes=5

Input grew 16 times (100 to 1,600) and the pairwise version did about 258 times more work, because n x (n-1) / 2 grows with the square. The set version did exactly 16 times more. That gap is the entire reason interviewers ask you to "do it in one pass".

Choose by the operations you need

Do not start with "which structure is best?". Start with a list of the operations your code performs most and match them to a structure that makes those cheap. The costs below are for CPython's built-ins.

One set of scans can answer several different questions, and each question suggests a different container. The snippet below uses a Counter for per-gate totals, dict.fromkeys to de-duplicate while keeping first-seen order, and a set comprehension for repeat entries.

from collections import Counter

# Scans from three gates, in arrival order
scans = [
    ("north", "W0007"), ("south", "W0012"), ("north", "W0007"),
    ("east",  "W0031"), ("south", "W0012"), ("north", "W0044"),
    ("south", "W0012"),
]

per_gate = Counter(gate for gate, _ in scans)
first_seen_order = list(dict.fromkeys(code for _, code in scans))
repeat_entries = {code for code, n in Counter(c for _, c in scans).items() if n > 1}

print(per_gate)
print(first_seen_order)
print(sorted(repeat_entries))

Counter({'north': 3, 'south': 3, 'east': 1})
['W0007', 'W0012', 'W0031', 'W0044']
['W0007', 'W0012']

Common mistakes

• Calling `in` on a list inside a loop. Symptom: the job takes a second at 1,000 rows, then minutes at 100,000, and the profiler points at a line that looks innocent. Build a set once, outside the loop.
• Using a list as a queue with `pop(0)`. Symptom: processing speed degrades steadily as the backlog grows. Every pop shifts the rest; use a deque (next lesson).
• Putting a list or dict into a set or as a dict key. Symptom: TypeError: unhashable type: 'list'. Convert to a tuple, or a frozenset when order does not matter.
• Expecting a set to keep order. Symptom: output order differs from the input, and may differ between runs for strings. Use dict.fromkeys or a list when order matters.
• Optimising before measuring. Symptom: clever code that saves nothing because the real cost was a database call. Count or profile first, then change structures.

How this shows up in real projects and interviews

In day-to-day work, most speedups come from one change: turn a list that is searched repeatedly into a set or dict, or stop re-sorting inside a loop. Code review comments like "this is quadratic once the table grows" are common. In interviews, you are usually asked for the time and space complexity of your own solution, and the expected move is to start with the obvious pairwise version, name its cost, and then improve it with a hash-based container. You pay for the speed with memory, so say that trade-off out loud. The same thinking continues in Arrays and Strings, and when ordering matters, in Sorting Algorithms. Next, the stacks and queues lesson covers the structures that decide order of processing.