Big-O Notation

The duplicate-order check had been fine for eighteen months. On every save it walked the customer’s orders looking for two with the same id, found none, and came back in a blink. Then one customer imported a back catalog — four thousand orders where the busiest account had ever held forty — and saving started to time out. Nobody had touched that function. The list got a hundred times longer, and the check got about ten thousand times slower.

The distance between “a hundred times more data” and “ten thousand times more work” is what Big-O notation exists to name. It does not measure how fast your code runs. It describes how the work grows when the input does, and those are different enough questions that the second one is the one that pages you at 3am.

Growth, not speed

Picture a door person checking arrivals against a guest list. Ask how long one check takes and you get an answer about that person, that clipboard, that evening. Ask what happens when the list goes from forty names to four thousand and you have learned something about the method, which a faster door person cannot change. Big-O is the second question.

So the notation throws away everything the second question does not depend on. Constant factors go: a method that takes 3n + 50 steps and one that takes n / 2 are both O(n), because both draw a straight line, and a straight line is a straight line however steep. Lower-order terms go with them — n² + 100n is O(n²), because once n is large enough the square swamps everything beside it. Put numbers in and you can watch it happen: at n = 10 the 100n term is ten times the square, 1,000 against 100; at n = 100 they tie at 10,000 each; at n = 10,000 it is 1,000,000 against 100,000,000, a rounding error.

What survives is the shape, and the shape is the durable part. It outlives the language you wrote it in, the machine you deployed it to, and the compiler that got better over the winter. Doubling your hardware moves a constant. It cannot turn a square into a line.

The shapes you will meet

Only a handful come up in ordinary work. Constant time, O(1), is work that does not depend on n at all: looking a key up in a hash table, reading array[7], pushing onto a stack. The door person has a pre-printed badge for each name and simply hands it over. Hash lookups are O(1) amortized, and only with a hash that spreads keys evenly — a bad one degrades toward a scan. Logarithmic time, O(log n), throws away half of what is left on every step: binary search over a sorted array, a lookup through a database index. Doubling n adds one step rather than doubling the steps, so a million items is twenty steps and a billion is thirty. That is the shape that makes large data tractable at all.

Linear time, O(n), is one unit of work per item — summing an array, filtering a list, reading a file. The door person reads the list top to bottom; twice the guests, twice the reading. Just above it sits O(n log n), which is the best a general-purpose comparison sort can do and what Array.prototype.sort gives you. It is close enough to linear that it rarely decides an argument.

Then there is quadratic time, O(n²): every item measured against every other item, which in code is almost always two loops with one nested inside the other. The door person asks each guest whether they know each other guest. This is the shape that ambushes people, because at forty items it is sixteen hundred units of work — imperceptible — and at four thousand items it is sixteen million.

The scene below runs three of those shapes over one order, and then doubles the list three times.

Each bar is one algorithm’s operation count, drawn against the same scale, so a bar twice as long is twice the work. At four orders they read 1, 4 and 16 — exactly what the three functions below do. Put a thousand orders in and the same three numbers become 1, one thousand, and one million.

Where the notation stops helping

Big-O is a statement about behavior as n grows without bound, which makes it deliberately silent about the n you actually have.

Constants matter in practice. Building a Set allocates memory and hashes every key; scanning an eight-element array touches eight neighboring slots and is finished before the hash function has warmed up. For small, fixed n an O(n) scan routinely beats an O(1) lookup, and the honest answer there is to measure rather than to reason from the notation. What the notation buys you is the other end: wherever the crossover sits, past it the scan loses and goes on losing.

It also hides which case you are being told about. Quicksort is O(n log n) on average and O(n²) in its worst case; a hash lookup is O(1) until every key collides in one bucket. When someone quotes a complexity, ask which case — and for anything holding input a stranger controls, the worst case is the one they get to choose.

It says nothing about memory either. An algorithm can trade one for the other, which is exactly what the Set below does: it spends O(n) space to buy O(1) lookups. Space complexity is written the same way and deserves to be stated alongside the time.

Here are the three functions the scene runs, at the middle size the scene passes through:

interface Order {
  id: string;
}

const orders: Order[] = [{ id: 'o1' }, { id: 'o2' }, { id: 'o3' }, { id: 'o4' }];
const ids = new Set(orders.map((order) => order.id));

/** One hash, one bucket: 1 operation at n = 4 and at n = 1,000,000. */
function hasId(id: string): boolean {
  return ids.has(id);
}

/** One comparison per order, so 4 when the id is absent: n operations. */
function findById(list: Order[], id: string): Order | undefined {
  for (const order of list) {
    if (order.id === id) return order;
  }
  return undefined;
}

/** Every ordered pair, so 4 × 4 = 16 iterations here: n² operations. */
function firstRepeatedId(list: Order[]): string | undefined {
  for (const a of list) {
    for (const b of list) {
      if (a !== b && a.id === b.id) return a.id;
    }
  }
  return undefined;
}

Count the loop bodies and you have the middle round of the scene: one, four, sixteen. The fix for firstRepeatedId is the trade hasId already made — keep a Set of the ids seen so far and check each order against it once. That turns sixteen into four here, and sixteen million into four thousand at the size that broke the save button.

function firstRepeatedId(list: Order[]): string | undefined {
  const seen = new Set<string>();
  for (const order of list) {
    if (seen.has(order.id)) return order.id;
    seen.add(order.id);
  }
  return undefined;
}

const backCatalog: Order[] = Array.from({ length: 4000 }, (_, i) => ({
  id: `o${i + 1}`,
}));
console.log(firstRepeatedId(backCatalog)); // undefined, after 4,000 checks
backCatalog.push({ id: 'o42' });
console.log(firstRepeatedId(backCatalog)); // o42