Counting steps
Big-O is about how the work grows as the input grows. The easiest way to feel it is to count. This check compares every pair of items: try 4, 8 and 16 items and watch the compare counter jump from 6 to 28 to 120.
7395
Does any value appear twice? Compare every pair. Watch the counter: for 4 items there are 6 pairs.
1function hasDuplicate(a) {2 for (let i = 0; i < a.length; i++) {3 for (let j = i + 1; j < a.length; j++) {4 if (a[i] === a[j]) return true;5 }6 }7 return false;8}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | 1 | the first two items match |
| average | n² | duplicates are rare or late |
| worst | n² | no duplicate: all n(n − 1)/2 pairs are checked |
| space | 1 | just the two loop indexes |
Where it breaks
- Doubling the input quadruples the work. 8 items need 28 compares and 16 need 120. At a million items it is about 500 billion, which is why n² code that is fine in a test falls over in production.
- Constants do not count. n(n − 1)/2 is about half of n², but Big-O drops the half. It describes how the cost grows, not the exact number of steps.
- The best case can mislead. Pick Early repeat: it stops after 2 compares. Big-O usually means the worst case, the input that makes the code work hardest. The fix for this one is a hash set, on the Finding duplicates page.