A First Taste of Algorithms · Two Questions
What a “step” is — a confession
We have been counting “comparisons” and calling it cost, and you are entitled to ask: who decided a comparison is one step? Comparing two numbers takes the machine some flicker of time; so does moving a finger. Why is each “one”?
The honest answer: counting steps requires choosing what to count, and the choice is a model — a deliberate simplification, made in the open. We count comparisons because, for searching, everything else the procedure does (moving fingers, checking whether they’ve crossed) happens at most once per comparison, so the comparison count tracks the true effort up to a constant factor we openly decline to chase. Different chapters will count different currencies: moves in Chapter 3, additions in Chapter 4, edge-visits in Chapter 5. The discipline is always the same — name your currency, count honestly in it, and let the shape of the growth (steady ramp, near-flat curve) be the conclusion, because the shape survives any reasonable change of currency. Lab 1’s last experiment, where counted steps and clocked seconds drew the same curves, is this confession verified.
Where this leaves us
Two questions — does it always work? what does it cost? — and one chapter’s worth of answers:
- Correctness means all inputs, and is established by argument, not demonstration. The argument has a standard form: a sentence kept true through every step.
- Cost is counted in a declared currency, and the worst case is the only promise available in advance.
- Absence is expensive for an unstructured list — and cheap for a structured one. Structure is purchased in advance and collected later; whether the purchase pays depends on how often you collect.
- Multiplying the problem can merely add to the cost — the logarithm’s signature, and the first hint of how dramatically cleverness can beat effort.
Binary search was clever, but its cleverness was bespoke — a trick fitted to one problem. What we want next is a strategy: a way of generating algorithms for problems we haven’t met yet. Chapter 2 takes up the most natural strategy there is — at every step, grab the option that looks best right now — and discovers that it is sometimes provably perfect and sometimes confidently, catastrophically wrong. Telling those two outcomes apart will not be a vibe. It will be a theorem.
Questions to talk about
No answer key. These are for arguing over, with someone who read the same chapter.
- Play the guessing game on 1 to 1000 with someone before reading on. Did ten questions suffice? What did it feel like when you believed it would work?
- The grinding strategy eliminates one suspect per question; halving eliminates fifty on its worst day. Why is the worst day the right thing to compare?
- The two questions are: does it always work, and how much work does it take? Apply both to a method you already use for something — revising, searching, tidying.
All 32 chapters of A First Taste of Algorithms · Foundations · All courses