What is Big O notation — and why your code flew on 100 rows and died on 100,000

Here's a familiar story. You built a comparison of two lists, tested it on 100 rows — instant. Then you loaded the real 100,000-row file, and the tab froze for a minute.

The code didn't break. It does exactly what it did before. There's just 1,000 times more data, and a million times more work. That gap is what Big O describes.

What Big O is

Big O is the answer to "how much does the work grow when the data grows." Not "how many milliseconds" — how it grows.

That matters. Milliseconds depend on your laptop. Growth depends on the code itself. If the code grows like a square, no fast processor will save you: double the data, quadruple the work.

It's written like this: O(n), O(n²), O(log n). The letter n is the size of the data. How many rows, users, products.

Four growth rates you'll actually meet

Almost everything you write fits into four classes.

• O(1) — constant. The work doesn't depend on size. Grabbing an array item by index, items[5], is one step whether there are 10 items or a million.
• O(log n) — logarithmic. Each step throws away half. A million items take about 20 steps. It's how you find a word in a dictionary: open the middle, decide left or right.
• O(n) — linear. One pass over all the data. Twice the data, twice the work. That's a plain loop or .filter().
• O(n²) — quadratic. A loop inside a loop. With 100 items it's 10,000 steps. With 100,000 it's already 10 billion.

That's the trap from the opening. On small data you can't see the difference between n and n². On big data it's the difference between a second and an hour.

Where the square hides

The sneaky part: O(n²) rarely looks like two nested for loops. More often it's hidden inside an ordinary method.

// find users that appear in both lists
const common = listA.filter(user => listB.includes(user))

It looks like one line and one pass. But includes is a loop too. It walks through listB until it finds a match. That's a pass inside a pass. Two lists of 100,000 — up to 10 billion comparisons.

The fix is swapping one structure:

const setB = new Set(listB)
const common = listA.filter(user => setB.has(user))

A Set doesn't search by walking — it looks things up by hash, in about one step on average. The code is now O(n). The same 100,000 rows take a fraction of a second.

A few more places where the square likes to hide:

• indexOf and find inside a loop — the same walk as includes.
• array.shift() in a loop. It removes the first item and shifts all the others. A queue built on shift() over a big array is quadratic again.
• Growing arrays or strings in a loop with spread — result = [...result, item] copies everything collected so far on every step.

What Big O doesn't tell you

Big O is a rough estimate, and that's fine. It drops the details on purpose.

• Constants don't count. Two passes over an array is still O(n). For growth, it doesn't matter.
• On small data it's not the main thing. If a list will never hold more than 50 items, includes in a loop is perfectly fine code. Don't turn every line into an optimization.
• It usually means the worst case. includes might find the item right away. But plan for walking the whole list.

A practical rule: think about Big O wherever data can grow. File imports, search, feeds, anything that comes from users.

How to use this with AI

AI writes filter + includes all the time — it's shorter. Ask it to check:

A good answer names a specific line and the "before/after" complexity. If the AI just rewrote everything "more nicely," ask it to prove where the square was. Then measure it to confirm it actually got faster.

Do I need Big O if AI writes my code?

Yes, at least the four classes. AI often picks the shortest code, not the fastest. To catch a square in review, the question "is there a loop inside a loop here?" is enough.

What does O(n log n) mean?

A bit slower than linear, but far faster than quadratic. That's the complexity of sorting: array.sort() in modern browsers runs in O(n log n). A million items sort in a fraction of a second.

Can Big O describe memory too?

Yes. The same notation estimates how much memory you need as data grows. The new Set(listB) above costs O(n) extra memory. Usually that's a fair trade: a little memory for a huge speed win.