Two tables, side by side. A million items: one algorithm needs a million checks, the other needs twenty. Today you put that difference into words — and learn the one situation where the slow one still wins.
No reading — this page is the reading. Runestone doesn’t cover Unit 4 (search, efficiency, limits, simulation), so everything you need is right here.
Programs, Algorithms region — end of Week 1. You have two search algorithms and two step-count tables. Today they meet, and 4.1’s missing vocabulary for “better” finally shows up.
| List size (n) | Linear — worst case | Binary — worst case |
|---|---|---|
| 10 | 10 | 4 |
| 100 | 100 | 7 |
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
Where does the binary number come from? Count how many times you can halve n before nothing is left. That’s a loop you can write:
n = 1000 steps = 0 while n >= 1: n = n // 2 steps = steps + 1 print(steps) # 10
n ← 1000 steps ← 0 REPEAT UNTIL (n < 1) { n ← (n - (n MOD 2)) / 2 steps ← steps + 1 } DISPLAY(steps)
1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1 → 0: ten halvings. That matches binary search’s worst case exactly — checked for every n from 1 to 5,000.
Pick a size, or keep pressing Double it. Watch one number explode and the other barely move.
That’s the word 4.1 was missing. Algorithm B from 4.1 wasn’t wrong. It was less efficient.
Five questions — “count the steps” items join the warm-up rotation starting today.
There are about 8 billion people on Earth. A sorted list of all of them could be searched in at most 33 checks. Linear search could need 8 billion.
That gap is why giant databases — license plates, faces, phone numbers, purchase histories — are useful at all. Efficient search is what makes it possible to look anyone up in an instant. Whether anyone should be able to is a question the algorithm can’t answer.