Big O — Measuring How Code Scales

What is it? #

Big O answers one question: as the amount of data grows, how does the amount of work grow with it?

It is not about seconds. A slow computer running good code beats a fast computer running bad code once the data is big enough. Big O describes the shape of that growth, not the speed of any particular machine.

You count the operations that grow with the input and ignore everything else. Constants and smaller terms get dropped, because at scale they stop mattering.

The reason to learn it is practical. It is the difference between a page that loads in 40 milliseconds with ten thousand users and one that times out — and you can usually predict which you have written before deploying.

Think of it like this #

Imagine looking for a friend's name in a phone book.

Flipping through every page from the start is one approach. With twice as many pages, it takes twice as long.

Opening the middle, deciding which half to keep, and repeating is another. Doubling the pages adds just one extra step.

Same task, completely different growth. That difference — not the speed of your fingers — is what Big O measures.

Simple example #

You have a list of users and you need to find one by ID. Scanning the list checks every user until it finds a match. Building a dictionary first lets you jump straight to the right entry. With 100 users the difference is invisible; with 100,000 inside a loop, one version finishes and the other does not.

Code #

users = [{"id": i, "name": f"user{i}"} for i in range(100_000)]

# O(n) — the work grows in step with the list
def find_by_scan(users, target_id):
    for user in users:          # up to 100,000 checks
        if user["id"] == target_id:
            return user
    return None

# O(1) lookup after an O(n) setup
index = {user["id"]: user for user in users}   # built once

def find_by_index(index, target_id):
    return index.get(target_id)                # one step, always

# O(n^2) — the classic accidental disaster
def find_duplicates_slow(items):
    dupes = []
    for i in range(len(items)):
        for j in range(i + 1, len(items)):     # a loop inside a loop
            if items[i] == items[j]:
                dupes.append(items[i])
    return dupes

# O(n) version of the same thing
def find_duplicates_fast(items):
    seen, dupes = set(), set()
    for item in items:
        if item in seen:
            dupes.add(item)
        seen.add(item)
    return list(dupes)

How the shapes grow as n goes from 10 to 1,000,000

O(1)        1            1              1           constant
O(log n)    3            10             20          halving each step
O(n)        10           1,000          1,000,000   one pass
O(n log n)  30           10,000         20,000,000  good sorting
O(n^2)      100          1,000,000      10^12       nested loops

How it works #

find_by_scan walks the list. If the match is last, it checks every item, so the work is proportional to the number of users. That is O(n) — linear.

find_by_index does one hash lookup regardless of size. That is O(1) — constant. The dictionary took O(n) to build, which is worth it the moment you look things up more than once. Build once, look up many times.

find_duplicates_slow has a loop inside a loop, and the inner one runs roughly n times for each outer pass. That is O(n²) — quadratic. At 1,000 items that is around half a million comparisons, which is fine. At 100,000 it is five billion, which is not.

find_duplicates_fast uses a set. Each membership check is constant time, and there is one pass, so the whole thing is O(n). Same answer, a completely different growth curve.

The table is the part worth remembering. Notice that O(log n) barely grows at all, and O(n²) explodes. Between them, O(n) and O(n log n) are the shapes most good code lands on.

One clarification that trips people up: Big O describes the worst case unless stated otherwise. A scan might find the item first try, but you plan for the case where it does not.

Real-world use #

This is not interview trivia. The most common real performance bug is an accidental O(n²): a loop over records that does a lookup inside the loop, or a database query per row instead of one query for all rows.

The fix is usually the same as above — build a dictionary or set first, then look up inside the loop. That one change has rescued countless slow endpoints.

Big O also explains why databases have indexes. Without one, finding a row means scanning the table, O(n). With one, it is a tree lookup, O(log n). On ten million rows that is the difference between seconds and milliseconds.

Space complexity follows the same notation and matters too. The dictionary in the example trades memory for speed, which is usually a good deal — until the data no longer fits in memory.

Common mistakes #

• Optimising code that runs on ten items. Big O only matters where n can grow.
• Missing the hidden loop: calling a function inside a loop that itself loops turns O(n) into O(n²).
• Forgetting that item in some_list is O(n). Inside a loop, that is quadratic.
• Assuming a lower Big O always wins. For small n, a simple O(n²) can beat a complex O(n log n).
• Ignoring memory. An O(1) lookup that requires a copy of the entire dataset has a cost too.

Practice #

Write a function that takes two lists and returns the values present in both. Write it first with nested loops, then again using a set. Time both with 10,000 items using time.perf_counter() and note the difference. Then say out loud what the Big O of each version is.