Time Complexity and Amortized Cost

The previous lesson showed that nested loops with a linear method inside them become quadratic. This one is about deriving a complexity claim yourself, on code you've never seen before, by literally counting operations — because "I have a feel for it" is exactly how a wrong complexity claim ends up in a pull request review.

The counting method

Take this function, which finds the closest pair of values in an array:

function closestPair(arr) {
  let best = Infinity;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      const diff = Math.abs(arr[i] - arr[j]);
      if (diff < best) best = diff;
    }
  }
  return best;
}

Count concretely. For arr.length = n:

• When i = 0, the inner loop runs n - 1 times.
• When i = 1, the inner loop runs n - 2 times.
• ...and so on, down to i = n - 2, where it runs once.

The total is (n-1) + (n-2) + ... + 1 + 0, which is the classic sum n(n-1)/2. Multiply that out: (n² - n) / 2.

Now apply the two rules of Big-O:

1. Drop constants. /2 doesn't change the shape of the curve as n grows — it just scales it. (n² - n) / 2 and n² - n describe the same growth shape.
2. Keep only the dominant term. As n grows large, n² completely dwarfs n — at n = 1,000,000, n² is a trillion and n is a million, a million-to-one gap. So the -n is irrelevant to the growth shape.

What's left is n². That's the complexity: O(n²). Not because "there are two loops" — nesting alone doesn't imply quadratic, as this lesson's third quiz question is designed to catch you on — but because you actually counted and the count came out proportional to n².

Nesting isn't the signal — the inner bound is

Compare that to this, which looks similarly nested:

function first10Products(arr) {
  const results = [];
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < 10; j++) {
      results.push(arr[i] * j);
    }
  }
  return results;
}

The inner loop always runs exactly 10 times, no matter how big arr is. Total work is 10n. Drop the constant 10 and you're left with n — this is O(n), linear, despite the visual nesting. The question to ask is never "how many loops" but "does the range of this loop depend on n, or is it fixed?"

Amortized cost: when the worst case lies to you

Now the trickier idea, and the one that actually explains a real engine behavior you rely on constantly: why is array.push() treated as O(1)?

A JS engine's array has a backing store with some capacity. Most pushes just write into the next free slot — genuinely O(1). But when the array is full, the engine has to allocate a new, larger backing store and copy every existing element into it. That single push is O(n), not O(1) — a real, worse cost.

If you only looked at that worst single push, you'd have to call the whole operation O(n). But that's the wrong question. The right question is: over a long sequence of pushes, what's the average cost per push?

Engines double the capacity on resize (roughly). That means a resize costing n copies only happens once every n pushes — the resizes get exponentially rarer as the array grows. Sum the total copying work across n pushes: it works out to roughly 2n copies total (a standard geometric series result), spread across n pushes. Divide: 2n / n = 2, a constant. Drop the constant and you get O(1) amortized — the average cost per operation across a long sequence, even though some individual operations cost more.

This matters beyond trivia: it's the same reasoning behind why a well-built Map or Set is described as O(1) average lookup despite occasional internal rehashing, and it's the honest answer to "isn't this technically sometimes slow?" — yes, rarely, and the average is what you should design around.

Run it and watch resizes grow logarithmically while averagePerPush stays roughly flat — that flatness is the entire proof of "amortized O(1)" made concrete instead of asserted.

What to remember

• Derive complexity by counting: write down how many times the innermost operation actually runs in terms of n, then drop constants and keep only the dominant term.
• Nested loops are not automatically O(n²) — a fixed-size inner loop keeps the whole thing linear. Always check whether the inner bound depends on n.
• Amortized analysis looks at total cost across a sequence of operations divided by the count, not the single worst operation.
• array.push() is amortized O(1): individual resizes cost O(n), but doubling capacity makes them exponentially rare, so the average cost per push across many pushes stays constant.