Card 01/ 08
Optimising a Solution: Remove the Waste in the Step That Dominates
Cost every step, find the one that sets the total, name what it wastes, and stop once no solution could be faster.
Optimising a working solution is a procedure of six steps: cost each step, find the one that dominates, meaning the step whose cost sets the total, compare it with the best conceivable runtime, the cost no solution can go below, and if there is a gap, name the waste in that step, remove it with a standard move and say what memory the move costs. It is step 4 of the six steps in the Solving an Unseen Problem topic, done in detail. The cue is having a correct answer that is too slow for the input size. A warehouse logs the order numbers 8 3 8 5 3 9 5 8 7, and the task is the first order number that appears only once. The first solution that comes to mind takes each number in turn and counts how often it appears by reading the whole list.
Which step of that solution dominates its cost?
The count. For each number it reads all n numbers, so up to n² comparisons in all, 81 for nine numbers if the only single were last; here it reaches 9 after 54. Everything else, taking each number and returning one, is O(n) at most.
Each step of the procedure produces one thing, shown here for the order numbers. The waste comes in three kinds, which Gayle Laakmann McDowell names bottlenecks, unnecessary work and duplicated work, BUD for short: a bottleneck is one step slower than the rest, unnecessary work computes something the answer never needs, and duplicated work computes the same thing more than once.
The six steps applied to the first single order number
1. Cost each step
Taking each number is O(n), counting one number is O(n), so the nested count is O(n²) and dominates.
2. State the best conceivable runtime
Every number must be read at least once, since any unread one might be the answer: O(n). This is the best conceivable runtime, BCR in McDowell's naming.
3. Compare
O(n²) is above O(n), so there is something to remove. Had the dominant step already been O(n), the procedure would stop here.
4. Name the waste
Duplicated work: 8 is counted from scratch each of the three times it appears, and every count rereads a list that has not changed.
5. Apply the standard move
A hash map of counts, built in one pass, then a second pass that returns the first number whose count is 1: 9 updates and 6 lookups.
6. State the memory, then cost again
The map holds one count per distinct number, 5 here, so O(d) extra memory. Both passes are O(n) on average, which matches step 2: stop.
The two solutions side by side, with what the faster one removes.
| Approach | Time | Space | What it removes |
|---|---|---|---|
| Count each number against the whole list | O(n²) | O(1) | Nothing |
| A hash map of counts, then a second pass | O(n) on average | O(d) for d distinct numbers | The repeated counting |
The standard moves are few, and each removes a known kind of waste: a hash set or map replaces a repeated search with one lookup; sorting puts related values next to each other; prefix sums answer any range total from one subtraction; two pointers walk a sorted array from both ends instead of trying every pair; memoisation stores the result of a repeated call; and a heap keeps the smallest or largest item ready without sorting everything. A trick that fits one problem can mislead on another: pairing values off with exclusive or finds a single value only when every other value appears exactly twice, and here 7 also appears once and 8 three times.
The procedure is like shortening a commute: find the leg that takes longest and fix that one, and stop when the trip is as short as the distance allows. The likeness breaks at the stopping point. The distance tells you the shortest possible trip but not that a route achieving it exists; the best conceivable runtime is a floor, and some problems never reach it.
- Complexity Analysis
- Performance
← → move through sections and cards