Name the brute force before you optimise anything

Write the obvious solution, cost it against the constraint, and if it does not fit, name the one line that is doing all the work.

The instinct on meeting a problem is to look for the clever solution. The reliable method is duller and much faster in practice: write the solution that tries everything, work out what it costs at the largest input allowed, and only then decide whether anything more is needed.

Here is a problem to run it on. A shop is offering a deal on any two items whose prices add up to exactly the target, and wants to know how many such pairs its price list contains. The obvious procedure examines every pair, and counts the pairs it examines as it goes.

Eight prices give 28 examined pairs, which is $8 \times 7 / 2$. Sixteen prices give 120, more than four times as many. The cost is $n(n-1)/2 = \Theta(n^2)$, and that number is now a fact rather than a feeling.

Cost it at the constraint, then decide

Suppose the price list can hold up to $2 \times 10^5$ entries. Then $n(n-1)/2$ is about $2 \times 10^{10}$, which at a hundred million operations a second is around 200 seconds. It does not fit, so something has to change. Suppose instead the list held at most 3000 entries: the count would be about $4.5 \times 10^6$, which finishes instantly, and the right move would be to keep the brute force and go home.

Naming the bottleneck

A bottleneck is the part of a procedure that accounts for its growth: the line executed the most times, or the phase whose cost dominates the sum of all the phases. Improving anything else is wasted effort, because the sum rule from earlier says the total grows like its largest term.

The bottleneck here is the inner loop, and it is worth stating in words rather than in code. For each price, it is asking: how many of the other prices are equal to target minus this one? The procedure asks that question $n$ times and answers it from scratch every time by walking the whole list.

Written that way, the fix is visible. Keep a tally of the prices already seen, so the question is answered by a lookup rather than by a walk.

Both procedures report 4 pairs. The first looked at 28 pairs, the second at 8 prices. At $n = 2 \times 10^5$ that is $2 \times 10^{10}$ against $2 \times 10^5$, and the second one finishes before you have lifted your hand from the keyboard.

The technique was not the point. What did the work was the sentence naming the bottleneck, because it separated the question being asked from the way it was being answered. Every optimisation in this course has that shape: find the question that is being answered repeatedly from scratch, and answer it once.

Keep the brute force

The fast procedure is harder to believe than the slow one. The slow one is a direct transcription of the problem statement, so if the two disagree on any input, the fast one is wrong. Testing one implementation against another on many random inputs is called differential testing, and it is the cheapest correctness check available.

1. Write the input/output contract in one sentence, including what the input is promised to satisfy.
2. Write the procedure that tries everything, however slow, and make it transparently correct rather than fast.
3. Count its cost as a function of $n$, and evaluate that count at the largest input the constraints allow.
4. If the number fits the budget, stop. A slow solution that finishes is finished work.
5. If it does not, name the bottleneck in words: which question is being answered repeatedly, and how many times.
6. Improve only the bottleneck, and check the result against the brute force on many small random inputs.