DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Part 2 of 16 · ~5 min

Big-O Complexity Analysis

The planner's first real feature lets a student search the catalog by typing part of a title:

function searchCatalog(query) {
  const hits = [];
  for (const section of CATALOG) {              // one pass, ~42,000 iterations
    if (section.title.includes(query)) hits.push(section);
  }
  return hits;
}

Nothing wrong there — a single pass over 42,000 items runs in a blink on any machine built this decade. The feature that follows it is where trouble starts: warn a student if their cart already has the same section added twice.

function hasDuplicateInCart(cart) {                    // cart: array of section codes
  for (let i = 0; i < cart.length; i++) {
    for (let j = i + 1; j < cart.length; j++) {         // this inner loop restarts for every i
      if (cart[i] === cart[j]) return true;
    }
  }
  return false;
}

A cart holds maybe eight sections, so this also feels instant — nothing here rings an alarm. But look at the shape rather than the speed: a loop nested inside another loop, both walking the same collection. That shape is invisible at eight items and expensive at forty thousand. Big-O is the vocabulary for describing shapes like this precisely: how running time and memory grow as input grows, once you throw away the constant-factor noise of "how fast is my laptop today."

Reading complexity straight off the code

One habit does most of the work here: sequential loops add their costs; nested loops multiply them.

function auditCart(cart) {
  let totalCredits = 0;
  for (const code of cart) totalCredits += creditsOf(code);   // pass 1

  let hasDup = false;
  for (const code of cart) if (seenOnce(code)) hasDup = true; // pass 2

  return { totalCredits, hasDup };
}

Two separate walks over the cart is n + n, which is 2n, which simplifies to O(n) once the constant multiplier is dropped — it doesn't change the curve's shape. hasDuplicateInCart above does something different in kind, not just in degree: an outer loop of length n wrapping an inner loop of length n does n × n work. That's O(n²). Before trusting a complexity estimate on sight, ask which of these two shapes you're actually looking at — loops back to back, or one buried inside the other.

The common complexity classes

Hold onto the last two rows — the recursion chapter builds a genuine O(2ⁿ) function by accident, and the dynamic-programming chapter shows exactly what fixing it costs. O(log n) deserves a separate note because its curve is so unlike the others: it appears whenever a step discards a constant fraction of what's left, the way each comparison in a binary search halves the remaining catalog. Double the catalog and a linear scan's work doubles too — but a binary search only gains one extra comparison. Different curve, not just a smaller constant.

Amortized cost: why the cart's push gets called "O(1) amortized"

Adding a section runs cart.push(section). Under the hood, a JavaScript array behaves like the growable list every language eventually implements: it reserves more room than it currently needs, and only reaches out to the operating system for a bigger block once that spare room actually runs dry — typically by doubling its capacity each time that happens:

// What push is roughly doing under the hood:
function push(dynArray, value) {
  if (dynArray.length === dynArray.capacity) {
    resizeTo(dynArray, dynArray.capacity * 2);   // O(n) — copies everything — but this is RARE
  }
  dynArray[dynArray.length++] = value;           // O(1) — happens every single call
}

Look at any one call to push on its own and its worst case is O(n) — whichever call gets unlucky enough to trigger the resize. Now zoom out and total the copying across an entire run instead: resizes land at sizes 1, 2, 4, 8, and so on up to n, and that whole geometric series adds up to somewhere under 2n. Spread across n pushes, that works out to a small, bounded amount of copying per push on average — nobody can point at any single push in advance and say "that one will be expensive," but the sequence as a whole never runs away on you. That's the entire content of the word "amortized": it describes a run of operations taken together, not a guarantee attached to any individual one. It's why an interviewer wants "amortized O(1)," not a bare "O(1)": the two claims aren't interchangeable, any more than searchCatalog being O(n) is the same claim as it being fast.

Carry one more fact forward from here: the call stack is memory too. A recursive call that goes n levels deep before its base case fires is holding O(n) space on the stack, whether or not it ever allocates an array. The recursion chapter turns that from an abstract warning into something you can point at directly.