Big-O & complexity

Big-O describes how an algorithm's work grows as the input grows. It deliberately ignores constants and hardware so you can compare shapes of growth. A loop that touches every element once is linear, written as order n. Nesting a second loop over the same data is order n squared. Halving the search space each step, the way binary search does, is order log n. The point is not the exact instruction count; it is what happens when n becomes large.

// order n: one pass
function sum(arr) {
  let total = 0;
  for (const x of arr) total += x;
  return total;
}

// order n squared: a pass for every element
function hasDuplicateSlow(arr) {
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++)
      if (arr[i] === arr[j]) return true;
  return false;
}

Why the structure matters more than the loop

The biggest wins rarely come from a tighter loop. They come from choosing a structure whose operations are cheaper. Looking up a key in a hash map is roughly constant time, while scanning an array for that same key is linear. Replace a linear scan inside a loop with a constant-time lookup and an order n squared algorithm collapses to order n. That single substitution is the engine behind most "I made it 100x faster" stories.

Space is a budget too

Complexity is not only about time. A hash map that turns a quadratic scan into a linear one spends extra memory to do it, which is order n space. Senior judgment is knowing when that trade is worth it. On a million-row hot path it usually is; on ten items it is noise. Always ask what n actually is in production before optimizing.

The challenge below counts the real work done by a linear scan versus a Map lookup and prints the comparison so you can see the gap widen with input size.

Next: the hash map, the single most useful tool in an interview.