Everyone greets everyone
O(n²) — Quadratic
The analogy
Now every guest must shake hands with every other guest. Ten guests is manageable; a hundred guests is not ten times worse, it is a hundred times worse. Nested loops over the same data feel fine in testing and fall over in production.
Visualizer
Everyone greets everyone
step 1 / 13| G1 | G2 | G3 | G4 | G5 | G6 | |
|---|---|---|---|---|---|---|
| G1 | — | |||||
| G2 | — | |||||
| G3 | — | |||||
| G4 | — | |||||
| G5 | — | |||||
| G6 | — |
Now every guest must greet every other guest. 6 × 6 pairings.greetings: 0
def everyone_greets_everyone(guests):
for a in guests:
for b in guests:
if a is not b:
shake(a, b) # n^2 handshakes
# 10 guests -> 90
# 100 guests -> 9_900 (100x, not 10x)Check yourself
Input goes from 100 to 1,000. An O(n²) algorithm does about…