Phase 1: Checking every pair of elements for duplicates

The Obvious Approach

You have an array of integers. Is any value repeated? The question sounds trivial — just compare everything. And that is exactly what brute force does: check every pair of elements. It is correct. It is also disastrously slow.

Think about what “check every pair” really means. For each element at index i, you compare it against every element at index j > i. The first element gets compared against 5 others. The second against 4 others. The third against 3. The total grows as n*(n-1)/2 — quadratic. For the array below, that is 15 pairs. Tap through them and feel the tedium build.

FIG. 1 — O(N²) PAIR EXPLOSION
Pairs checked: 0 / 15
3
0
1
1
4
2
1
3
5
4
9
5