Big-O Is One Question: How Fast Does the Work Grow?

"Big-O sounds like a fraternity. It's actually the least intimidating idea in computer science: if I double the data, what happens to the work?"

Strip the Scary Off It

People treat Big-O like a secret handshake. It isn't. The 'O' just means "on the order of" — a rough description of the growth shape, ignoring details that don't matter at scale. Every Big-O you'll ever meet answers a single question: when the input doubles, what happens to the amount of work?

That's it. Three of the most common answers tell you almost everything:

O(1) — constant. Double the data, work stays the same. Looking up a word in a dict doesn't care if the dict has 10 entries or 10 million.
O(n) — linear. Double the data, double the work. Reading every item in a list once.
O(n²) — quadratic. Double the data, quadruple the work. Comparing every item to every other item.

The Doubling Test

Here's a trick that makes complexity physical instead of abstract. Take any function, run it on n items, then run it on 2n items, and watch what the work does:

Work unchanged? O(1).
Work doubled? O(n).
Work × 4? O(n²).
Work grew by just a fixed amount (one extra step)? O(log n) — the magical one we'll meet soon.

You can run this test in your head while reading code, or literally in a counter like the snippet below. Once doubling becomes a reflex, you read complexity straight off the page.

Big-O answers exactly one question: as the input grows, how does the work grow with it? Constant, linear, quadratic — the shape of that growth is the whole vocabulary.

Why We Throw Away the Junk

Big-O deliberately ignores constants and small terms. An algorithm that does 2n + 7 steps is still O(n) — because when n hits a million, the 2 and the 7 are invisible next to the n. We're not being sloppy; we're focusing on the only thing that decides whether the code survives at scale: the dominant shape. (The next lesson shows you how to read that shape straight out of loops.)

Pippa's Confession

Big-O intimidated me until Dad reduced it to four words: "double it, watch work." Suddenly the Greek-looking notation was just a label for something I could feel by running the code twice. I stopped reciting "O of n" like a spell and started actually seeing the doubling. The notation is the destination; the doubling test is the road.

Code

The doubling test in numbers·python

# The doubling test, made literal. Run on n, then 2n, watch the work.

def work_constant(items):      # O(1): peek at the first item
    return 1                    # one step, no matter how many items

def work_linear(items):        # O(n): touch every item once
    return len(items)           # n steps

def work_quadratic(items):     # O(n^2): every pair
    n = len(items)
    return n * n                 # n*n steps

for n in (1_000, 2_000):       # n, then 2n
    items = list(range(n))
    print(f"n={n:>5} | O(1)={work_constant(items):>2}  "
          f"O(n)={work_linear(items):>5}  O(n^2)={work_quadratic(items):>10}")

# Doubling n:  O(1) stayed 1.  O(n) doubled.  O(n^2) went up 4x.
# That ratio IS the complexity. No stopwatch required.

Exercise

For each, say the Big-O without code: (1) finding the max in an unsorted list of n numbers, (2) checking if the first element equals the last, (3) for each person in a room of n, shaking hands with every other person. Then predict: if n doubles, what happens to the work in each case?

Hint

Count how many items each one touches. (2) touches two items regardless of n. (3) is every-pair — that's the quadratic one.

Strip the Scary Off It

The Doubling Test

Why We Throw Away the Junk

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0