Lesson 9 of 11
The big picture
Show on a big screenEvery count here was worked out from the rules in the lessons.
| Idea | Remember | Example |
|---|---|---|
| Is it there at all? | Say true when you find it. Say false after the whole walk. | 21 rupees gives false |
| The counted loop | Init, test, update. A loop that runs to its end tests once more than it runs the body. | i ends at 3 |
| In order first | Check the middle. Halving needs a sorted list. | 24 is at position 4 |
| Counting both searches | Count comparisons. In the worst case, doubling adds one to halving. | 64 fares: 64 and 7 |
| One pass of selection | Find the smallest. Swap it to the front through a temp box. | 18 moves to the front |
| The whole sort | Repeat the pass. Five crates need four passes. | 10 comparisons |
| Sort once, search many | Sorting is paid once. Count the questions first. | 6 questions: 42 or 39 |
| How the count grows | In the worst case, the walk doubles. Halving adds one. Sorting grows about four times. | 28, 120, 496, 2,016 |
The numbers here count comparisons, not seconds.