How fast is fast? Big-O

It worked on 10 items…

Your code finds duplicates in a list of 10 orders instantly. With 100,000 orders the page freezes. The difference isn't the computer — it's how the number of steps grows with the input. Big-O notation describes that growth.

Counting steps

function first(list) {
  return list[0];                 // O(1): one step, any size
}

function sum(list) {
  let total = 0;
  for (const x of list) total += x; // O(n): one step per item
  return total;
}

function hasDuplicate(list) {
  for (let i = 0; i < list.length; i++)
    for (let j = i + 1; j < list.length; j++)
      if (list[i] === list[j]) return true; // O(n²): pairs of items
  return false;
}

for (const n of [10, 1000, 100000]) {
  console.log(n, "items → n² =", (n * n).toLocaleString(), "comparisons, log₂ n ≈", Math.round(Math.log2(n)));
}

Drop constants: 3n + 5 is O(n).
Keep the biggest term: n² + n is O(n²).
Space complexity counts extra memory the same way.

It worked on 10 items…

Counting steps

The rest of this lesson