Complexity Intuition

Mental model: Big-O is not a speed. It is the shape of the line you get when you double the input. Constants decide whether you notice today, the shape decides whether you are doomed later.

Level: advanced · about 18 minutes

A table renders instantly with 50 rows, fine with 500, and locks the tab for four seconds with 5,000. Nothing broke between those runs. The code always had the same shape, and you only crossed the point where the shape started to cost more than the constant factors were hiding.

Count the work, not the milliseconds

Timings depend on your laptop, your battery mode and what Chrome is doing in another tab. Operation counts do not. So the first move is always to count: for an input of size n, how many times does the innermost line run?

function countLinear(n) {
  let ops = 0;
  for (let i = 0; i < n; i += 1) ops += 1;
  return ops;
}

function countNested(n) {
  let ops = 0;
  for (let i = 0; i < n; i += 1) {
    for (let j = 0; j < n; j += 1) ops += 1;
  }
  return ops;
}

for (const n of [10, 100, 1000]) {
  console.log('n =', n, '| linear', countLinear(n), '| nested', countNested(n));
}
// -> n = 10   | linear 10   | nested 100
// -> n = 100  | linear 100  | nested 10000
// -> n = 1000 | linear 1000 | nested 1000000

The same question asked two ways. Watch the second column, not the first.

Ten times the input, ten times the work for the first one and a hundred times for the second. That relationship is all big-O records. O(n) means the work grows in step with the input, O(n squared) means it grows with the square. We write the second as O(n^2), and by convention we throw away constants and lower-order terms: 3n^2 + 500n + 12 is just O(n^2), because as n grows the squared term buries everything else. Big-O is a statement about growth, not about speed. An O(n^2) function can beat an O(n) one on small inputs all day, and often does.

Read the n = 1,000,000 column as a rough time budget. A modern engine does something in the order of 100 million simple operations per second in a tight loop, so a million is about 10 milliseconds and you will not notice it. A trillion (O(n^2) at a million) is roughly three hours. That is the whole reason anyone cares: the difference between the rows is not a percentage, it is a difference of kind.

Measure, do not guess

performance.now() returns a high resolution timestamp in milliseconds, as a float, counted from when the page loaded. Two readings and a subtraction give you the elapsed time of anything.

for (const n of [1000, 2000, 4000, 8000]) {
  const arr = Array.from({ length: n }, (_, i) => i);
  const set = new Set(arr);
  const probes = Array.from({ length: 500 }, (_, i) => Math.floor((i * n) / 500));

  let t0 = performance.now();
  let hits = 0;
  for (const p of probes) if (arr.includes(p)) hits += 1;
  const scan = performance.now() - t0;

  t0 = performance.now();
  hits = 0;
  for (const p of probes) if (set.has(p)) hits += 1;
  const hash = performance.now() - t0;

  console.log('n =', n, '| includes', scan.toFixed(2) + 'ms', '| set.has', hash.toFixed(3) + 'ms');
}
// -> n = 1000 | includes 0.82ms | set.has 0.118ms
// -> n = 2000 | includes 1.25ms | set.has 0.142ms
// -> n = 4000 | includes 2.82ms | set.has 0.176ms
// -> n = 8000 | includes 7.04ms | set.has 0.355ms

Linear scan versus hashed lookup, same data, growing n. Numbers vary by machine.

The number of lookups is fixed at 500 in every run, so the only thing changing is how much work each lookup does. includes walks the array until it finds the value, so doubling the array roughly doubles the column. Set.prototype.has hashes the key and jumps straight to a bucket, so its column barely moves. That flat line is what O(1) looks like in a measurement, and the wobble in it is your reminder that real timings are noisy.

Why push is cheap and shift is not

This is the single most valuable piece of complexity knowledge for everyday JavaScript, because the expensive call looks exactly as innocent as the cheap one.

for (const n of [10000, 20000, 40000]) {
  const source = Array.from({ length: n }, (_, i) => i);

  const a = source.slice();
  const outA = [];
  let t0 = performance.now();
  while (a.length) outA.push(a.pop());       // from the end
  const fromEnd = performance.now() - t0;

  const b = source.slice();
  const outB = [];
  t0 = performance.now();
  while (b.length) outB.push(b.shift());     // from the front
  const fromFront = performance.now() - t0;

  console.log('n =', n, '| pop', fromEnd.toFixed(1) + 'ms', '| shift', fromFront.toFixed(1) + 'ms');
}
// -> n = 10000 | pop 3.5ms  | shift 5.7ms
// -> n = 20000 | pop 14.5ms | shift 419.3ms
// -> n = 40000 | pop 2.2ms  | shift 1075.0ms

Draining the same array from the end and from the front. Give this one a second or two.

A JavaScript array is a contiguous block of slots plus a length, and element i lives at a fixed offset from the start. push writes one slot past the end and bumps the length: constant work. When the block runs out of room the engine allocates a bigger one (typically around 1.5 to 2 times the size) and copies everything across, which is O(n), but it happens once per doubling. Spread across all the pushes that copy costs a constant amount each, which is what amortised O(1) means: any single push may be expensive, n pushes together are O(n).

shift cannot play that trick. Removing element 0 means every remaining element must move down one index, because indices are positions, not labels. That is O(n) per call, so draining an array of n items with shift is O(n^2). In the measurement above, doubling n from 20,000 to 40,000 multiplied the shift time by about 2.6, and the next doubling by another 3.3. Engines do optimise the small and simple cases (that is why n = 10,000 looks harmless), so the honest rule is: shift and unshift and splice(0, ...) are linear by specification, engines sometimes hide it, and you should never build a queue on the assumption that they will.

const n = 200000;
const a = Array.from({ length: n }, (_, i) => i);
const b = a.slice();

// A: while (a.length) a.pop();
// B: while (b.length) b.shift();
// Roughly how do the two times compare?

pop is O(1) per call, so A is O(n) overall: a few milliseconds. shift is O(n) per call, so B is O(n^2): at 200,000 elements that is tens of billions of element moves, tens of seconds. The gap is not a constant factor, it grows with n, which is why nothing you tune inside the loop will save it.

Best, average, worst and amortised

One label per operation is a simplification. Map.prototype.get is O(1) on average, but a hash table with every key landing in the same bucket degrades to O(n), and that is exactly how hash-collision denial of service attacks work. Quicksort is O(n log n) on average and O(n^2) on an already-sorted input if you pick pivots badly. When someone states a complexity without a qualifier they almost always mean average or amortised.

When it starts to matter

Big-O ignores constants, and constants are what you feel at small n. Building a Set allocates, hashes every key and touches memory the array scan never touches. Below some crossover point the theoretically worse algorithm wins.

function bench(fn, reps) {
  for (let i = 0; i < 50; i += 1) fn();          // let the JIT warm up
  const t0 = performance.now();
  for (let i = 0; i < reps; i += 1) fn();
  return performance.now() - t0;
}

for (const n of [8, 16, 64, 256]) {
  const arr = Array.from({ length: n }, (_, i) => i);

  const scan = bench(() => {
    let hits = 0;
    for (let i = 0; i < n; i += 1) if (arr.includes(i)) hits += 1;
    return hits;
  }, 2000);

  const hash = bench(() => {
    const set = new Set(arr);                    // build cost included, deliberately
    let hits = 0;
    for (let i = 0; i < n; i += 1) if (set.has(i)) hits += 1;
    return hits;
  }, 2000);

  console.log('n =', String(n).padStart(4), '| scan', scan.toFixed(1) + 'ms', '| hash', hash.toFixed(1) + 'ms');
}
// -> n =    8 | scan 6.1ms   | hash 3.0ms
// -> n =   16 | scan 4.1ms   | hash 7.4ms
// -> n =   64 | scan 14.2ms  | hash 18.4ms
// -> n =  256 | scan 308.0ms | hash 85.3ms

n lookups over n items: scan the array, or build a Set first? Run it twice, the small rows move.

Below about 64 items the two are indistinguishable and the ordering flips between runs, which is the honest answer to "which is faster": neither, measurably. By 256 the hashed version is about three times quicker, by 1,000 it is roughly ten times, and from there the gap only widens. So the rule is not "always use a Set". It is: for a handful of items write whatever reads best, and once a collection can grow without a bound you control, pick the shape that will not betray you at 100,000.

1. Reproduce the slowness first Record a profile and find the function that actually costs the time. Intuition about which line is hot is wrong often enough to be worthless.
2. Time the smallest thing you can Two performance.now() readings around the suspect call. Log the elapsed value, do not eyeball it.
3. Warm up, then repeat The first few calls run in the interpreter before the optimiser kicks in. Discard those, then run enough repetitions that the total is at least a few milliseconds.
4. Use the result An optimiser that can prove a value is never read is allowed to delete the work. Return or accumulate the value so the benchmark measures something real.
5. Double n and look at the ratio This is the measurement that tells you the class. Same time means O(1), double means O(n), quadruple means O(n squared).

Try it yourself

Print the growth table yourself

const classes = {
  'O(1)': () => 1,
  'O(log n)': (n) => Math.ceil(Math.log2(n)),
  'O(n)': (n) => n,
  'O(n log n)': (n) => Math.round(n * Math.log2(n)),
  'O(n^2)': (n) => n * n,
};

const OPS_PER_SECOND = 1e8;   // a rough figure for a tight loop in a modern engine

for (const n of [10, 100, 1000, 10000]) {
  const row = Object.entries(classes)
    .map(([label, f]) => label + ': ' + f(n).toExponential(1))
    .join('  |  ');
  console.log('n =', n, '->', row);
}

const seconds = (ops) => (ops / OPS_PER_SECOND).toFixed(3) + 's';
console.log('n^2 at n = 1e6 takes about', seconds(1e12));

Push n to 100000 and watch which columns are still readable. Then add an O(n^3) column and find the n where it passes 10^12.

Name the class from the ratios

function mystery(arr) {
  // change me: a scan, a sort, a nested loop
  let total = 0;
  for (const v of arr) total += v;
  return total;
}

function timeAt(n) {
  const arr = Array.from({ length: n }, (_, i) => i);
  for (let i = 0; i < 20; i += 1) mystery(arr);        // warmup
  const t0 = performance.now();
  for (let i = 0; i < 200; i += 1) mystery(arr);
  return performance.now() - t0;
}

let previous = null;
for (const n of [2000, 4000, 8000, 16000]) {
  const ms = timeAt(n);
  const ratio = previous ? (ms / previous).toFixed(2) : '-';
  console.log('n =', n, '|', ms.toFixed(2) + 'ms', '| ratio vs previous:', ratio);
  previous = ms;
}
// ratio near 1 -> O(1) or O(log n)
// ratio near 2 -> O(n)
// ratio near 2.2 -> O(n log n)
// ratio near 4 -> O(n^2)

Replace the body of mystery with arr.sort((a, b) => a - b) on a shuffled copy and see whether you can tell O(n log n) from O(n) by ratio alone. Then try a nested loop.

Exercises

Find a duplicate without the nested loop

Write hasDuplicate(values) which returns true when any value appears more than once, and false otherwise. It must run in O(n) time, so it has to survive an array of 100,000 distinct numbers without the test timing out. Treat NaN as equal to itself, and keep 1 and '1' distinct.

Binary search, counted in probes

A sorted source is { length, get(i) }, so reading an element is a call you can count. Write binarySearch(source, target) returning the index of target, or -1 when it is absent. It must be O(log n): for a million entries the tests allow at most 25 calls to get.

Check yourself

What is the complexity of items.filter((x) => others.includes(x.id)) for n items and m others?

O(n * m) — filter visits every item once, and each visit runs includes, which scans up to m others. Multiply them: O(n * m), which is quadratic when the two lists grow together. Building new Set(others) first costs O(m) once and turns the check into O(1), giving O(n + m) overall.

What does this print, roughly, and why?

hundreds of milliseconds or more, because each shift renumbers the rest — Each shift moves every remaining element down one index, so the loop does about 50,000 * 25,000 element moves. Measured earlier in this lesson, 40,000 elements took around a second. The while condition is fine: shift on an empty array returns undefined and never throws, and the loop just ends.

You benchmark two functions at n = 20 and the O(n^2) one is faster. What should you conclude?

nothing is wrong: constants dominate at small n, and 20 is small — Big-O describes growth as n goes up, not which function wins at a fixed small n. The linear version may allocate a Set or a Map, and that constant cost is real. The question that matters is whether n stays small. Doubling n a few times and watching the ratio tells you which side of the crossover you are on.

Which statement about push is precisely correct?

push is amortised O(1): individual calls can be O(n), but n pushes cost O(n) in total — Most pushes write one slot and bump the length. When the backing store is full the engine allocates a larger one and copies, which is O(n) for that one call. Because the capacity grows by a multiple rather than by a fixed amount, those copies get rarer as the array grows, and the total cost of n pushes stays O(n). Divided over the calls, that is constant each: amortised O(1).

Common mistakes

• Optimising a loop that runs 20 times while an O(n^2) join sits untouched two functions away.
• Building a queue on shift, which is correct and quietly quadratic.
• Calling includes or find inside filter or map, which multiplies the two lengths together.
• Benchmarking without a warmup, so you are timing the interpreter rather than the optimised code.
• Benchmarking a pure function and throwing the result away, letting the engine delete the work.
• Quoting O(1) for Map lookup as if it were a guarantee. It is an average, and adversarial keys can break it.
• Assuming a smaller big-O is always the faster code. Constants exist, and small n is most code.

Takeaways

• Big-O is the shape of the curve when you double the input, not a speed in milliseconds.
• Drop constants and lower-order terms: 3n^2 + 500n is O(n^2).
• Indexing, push and pop are constant. shift, unshift and splice(0, ...) are linear because indices are positions.
• Amortised O(1) means occasional expensive calls averaged over many cheap ones, as with array growth.
• Map and Set lookups are constant on average, linear in a pathological collision case.
• Measure with performance.now, warm up first, use the result, and read the ratio as you double n.
• Below the crossover point the worse class often wins. Above it, no amount of tuning helps.