Lesson 4 of 11
Counting both searches
Show on a big screenTwo searches, one board. Which one does less work? The worst case is when a search needs the most checks.
Step 1 of 4
- 8 fares: walk 8, halving 4.
- 16 fares: walk 16, halving 5.
- 32 fares: walk 32, halving 6.
- 64 fares: walk 64, halving 7.
The rule
Halving does less work. The gap grows as the list grows.
Count comparisons, not seconds. In the worst case, doubling the list doubles the walk. It adds one comparison to halving.
A comparison is one check of an item against the wanted fare. We count these because a clock changes from phone to phone.
The walk is worst when the fare is last, or missing. It then checks every fare. Halving is worst for a missing fare. It halves the list until nothing is left.
| Fares on the board | The walk | Halving |
|---|---|---|
| 8 | 8 | 4 |
| 16 | 16 | 5 |
| 32 | 32 | 6 |
| 64 | 64 | 7 |
The walk's count grows as fast as the list. Halving's count grows slowly.
Guess the halving count. Then read both bars.
Loading lab…
Try the lab to finish this lesson.