Counting Steps
Two chefs both cook a perfect dinner for four. Chef A preps each guest's plate separately: 4 guests, 4 rounds of work. Chef B insists on personally introducing every plate to every other plate: 4 plates but 16 comparisons. At a dinner party nobody notices the difference. At a 500-guest wedding, Chef A does 500 units of work — Chef B does 250,000 and the kitchen is on fire. The lesson: do not ask "is my code fast on my laptop today?" — ask "what happens to the step count when the input gets 100 times bigger?" A single loop grows politely with the guest list. A loop INSIDE a loop grows with its square. You now know enough to smell slow code from across the room; Module 4 will give the smell its proper name: Big O.
Two chefs, one wedding
step 1 / 5Chef A preps each plate once: 8 guests, 8 units of work. Double the guests, double the work — a straight, honest line.one loop -> linear
The growth table — steps at different n
| shape | n = 10 | n = 1,000 | n = 1,000,000 | smell |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | array index, hash lookup |
| O(log n) | ~3 | ~10 | ~20 | halving each step |
| O(n) | 10 | 1,000 | 1,000,000 | one loop |
| O(n log n) | ~33 | ~10,000 | ~20,000,000 | sort-shaped |
| O(n²) | 100 | 1,000,000 | 10¹² — days | loop inside a loop |
Counting rules
- Sequential loops ADD (n + n = still O(n)); nested loops over the same data MULTIPLY (n × n).
- A hidden loop counts: `x in list` (Python) and array.includes (JS) are O(n) scans — inside a loop they quietly build O(n²).
- Halving is the signature of log n: 1,000,000 → 20 steps. If your algorithm throws half away each round, it's logarithmic.
- Constants are invisible to growth but real to users — Module 4 formalises when they matter.
# Chef A — one pass: n steps
for guest in guests:
prep(guest)
# Chef B — all pairs: ~n*n/2 steps. Alarm bells!
for a in guests:
for b in guests:
if a != b and a.email == b.email:
print("duplicate!")
# The escape (Module 2 preview): one pass + a set
seen = set()
for g in guests:
if g.email in seen: print("duplicate!")
seen.add(g.email)A function checks every pair of users for duplicate emails among n users. Roughly how does its work grow?
has_duplicate(emails) returns True if any email appears twice. Chef A style please: ONE pass with a set — no nested loops.