You optimized a daily-totals pass and it runs faster - how do you verify it is still correct?

## Why verification is a separate step, not a feeling The failure mode this step exists to prevent has a specific shape: *the idea is right and it is faster, so it must be correct.* Both halves of that can be true while the code is wrong, because an optimization does not merely make the same computation cheaper - it usually replaces it with a different computation that is supposed to agree. Agreement is a claim, and claims get checked. Optimizing a per-day rescan into a single carrying pass is a good illustration. The naive version recomputes each day independently, so its risk is only "did I select the right rows." The optimized version threads an accumulator through the whole input, so its risk becomes "is the carried state correct at every transition." **The optimization moved the boundaries.** Verifying the new code at the old code's weak points finds nothing. ## State the invariant before you trace A dry run without an invariant is just re-reading the code and agreeing with yourself. Write down the property that must hold at a specific instant, in terms of the state variables: > At the moment a day's closing total is recorded, the accumulator holds exactly the sum of rows dated on or before that day. Now the trace has something to fail against. Walk the worked example row by row and, at each write, ask whether the invariant is true right then. The classic bug in this shape is an ordering fault: the loop adds the current row to the accumulator, *then* notices the date changed and writes the previous day's close. The first row of the new day is inside the accumulator at that moment, so it is counted in the day that just closed - and, because the accumulator carries forward, it is counted again in the day it belongs to. The output is not obviously broken; it is one row wrong at each rollover, which is exactly the kind of defect a report ships with for months. Fixing it is a one-line reordering - record the close *before* adding the row that opened the new day - but you only find it by pointing at the instant the invariant is supposed to hold. ## The transitions worth walking For any pass that carries state across grouped input, the same short list catches most of it: - **The very first row**: is the state initialized from data that has not been consumed yet, or from data you are about to consume twice? - **Every group change**: the invariant check above. - **After the loop**: the final group has no successor to trigger its write. A missing tail write loses the last day entirely - a bug that hides whenever your test example happens to end on a group boundary. - **An empty group**: a day with no transactions. A carrying pass has nothing to trigger on, so the day is either absent or silently reported with the previous day's number, and those are very different wrongs. - **Empty input**: does the initialization even have a first row to read? - **Unordered input**: the pass may assume rows arrive grouped. If that assumption is new - the rescan version did not need it - it is part of the change and belongs in the verification, not in the reader's imagination. ## What a matching answer on one example does and does not prove If the optimized version reproduces your hand-computed numbers, you have learned that the two agree **on that input**. That is genuinely worth having, and it is why the worked example from earlier in the method gets reused rather than replaced by a fresh one - a new example tests new territory and quietly leaves the original untested. But agreement on one input is evidence, not proof, and it is weakest exactly where optimizations break: your example probably has no empty group, no tie at a boundary, and no rows out of order. So pick the next example deliberately, aimed at the transitions the optimization introduced: one that ends mid-day, one with a gap day, one with two rows sharing the boundary instant. Three tiny targeted traces beat one long generic one. ## Verifying the cost claim too Verification covers the complexity you claimed as well as the answer you produced. Re-derive it from the code you actually wrote - count the passes, count the auxiliary structures, and include recursion depth if any, because stack space is space. It is common to claim a single-pass linear solution and then notice an inner scan hiding inside a helper, which quietly restores the cost you thought you had removed. ## Saying it out loud In an interview, narrate the dry run: name the invariant, walk the two or three interesting rows, and say what you are checking at each one. That is a small speech, it takes under a minute, and it is one of the strongest signals available at this stage - because the alternative, "I think that's right, it's faster now," is precisely the answer the step was designed to prevent.