Inner work multiplies

Picture a teacher checking homework: for each of n students (the outer loop), she reads all n pages of the textbook (the inner loop). That is n times n pages read.

When one loop sits inside another, the inner loop runs completely on every pass of the outer one. n passes around n passes is n × n work, which we call O(n²).

n × n: when both loops run over all n values.

n = 4: every pair (i, j) with i < j gets a ✓ when the inner body runs

j = 0j = 1j = 2j = 3

i = 0

✓

i = 1

i = 2

i = 3

runs: 3

i = 0: the inner loop runs j = 1, 2, 3. Three times.

Move 1 of 5

Every pair once

A common shape starts the inner loop just after the outer one, so every pair of positions is looked at once. Think of every handshake in a room: each pair shakes hands once, not twice.

The inner loop runs n − 1 times, then n − 2, then down to 0. That adds up to n × (n − 1) ÷ 2: about half of n², which is still O(n²).

n × (n − 1) ÷ 2: is the number of pairs.

Use a long: a 32-bit count passes two billion once n passes about 65,000.

In code

return n * (n - 1) // 2