Loops inside loops
Count the work of a loop nested in another loop. About 8 minutes.
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²).
- runs
- 3
i = 0: the inner loop runs j = 1, 2, 3. Three times.
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²).
return n * (n - 1) // 2
For n = 4, the outer loop runs i = 0..3 and the inner loop runs j = i + 1..3. How many times does the inner body run?
- A6
- B16
- C12
Show the answer
6. 3 + 2 + 1 + 0 = 6, which is 4 × 3 ÷ 2.
Count the pair checks
This code looks at every pair of positions once: the outer loop runs i from 0 to n − 1, and the inner loop runs j from i + 1 to n − 1. Return how many times the inner body runs. n can be ten million, so count instead of looping.
n = 4 → 6
0 ≤ n ≤ 10,000,000 · the answer can pass two billion, so return a long