Judging Append by Its Slowest Call

One append to a dynamic array can copy every element, and it is tempting to call append O(n) because of it. This card covers why that judgement is wrong, by counting the copies of 16 appends one call at a time and averaging them.

The symptom is a review comment saying a loop of appends is quadratic, because the slowest append in it copies the whole array. The trigger is judging an operation by its worst single call when it is always called many times in a row.

The second column is the call on its own; the last is the call judged as part of the sequence.

Append 9 copies eight elements, the most of any call, yet the average never passes 1.67. Each expensive call comes after enough cheap ones to pay for it. Charge every append three units: one for its own write and two saved. When the array doubles from capacity m to 2m, the m/2 appends since the last move have saved m units, exactly enough to copy the m elements. The same run went further: 1,000 appends made 1,023 copies with a slowest call of 512, and 1,000,000 appends made 1,048,575 with a slowest call of 524,288, an average of 1.02 and 1.05 copies per append.

The cost of the mistake is a worse design. Someone calls a list of appends quadratic, then avoids the cheapest structure for building a sequence, or replaces it with one that is slower at reading by position.

Judge an operation that runs in sequence by its total over the sequence divided by its length, its amortised cost. Keep the worst single call for where one call's delay matters on its own, such as a request with a deadline, and there reserve the capacity in advance, as Java's new ArrayList<>(initialCapacity) does, so that no append has to move.