See how a growing backtest buffer can have constant amortised append cost even when copying records makes a single append expensive.
Amortised algorithm analysis
Amortised algorithm analysis bounds the total cost of a sequence of operations and expresses that bound per operation. The bound applies to every allowed sequence from the stated starting state. In a backtest that appends one result per event, it can show that the work of building a buffer grows linearly with the number of results, even though an individual append can be expensive. The average divides work by the number of operations. An average-case time complexity claim instead takes an expectation under a probability model.
Eight appends, three doublings
Start an illustrative backtest buffer with zero slots. The first append allocates one slot. After that, each append to a full buffer doubles its capacity, copies the existing records and writes the new record. Count one unit per record copied or written and leave allocation itself outside this count.
The fifth append grows capacity from four to eight. It copies four records and writes one, costing five units. The full eight-append run costs 15 units: eight writes plus seven copies. The average over this run is 15/8=1.875 units per append.
Stacked bars show append costs of 1, 2, 3, 1, 5, 1, 1 and 1 work units. Append 5 copies four records and writes one. The eight appends total 15 units.
The solid base is the new write. Each outlined block above it is one existing record copied during a resize.
Why the bound holds for any run length
The aggregate method counts all the copies together. If the largest full buffer copied during n appends held m records, the nonzero copy counts are the powers of two from 1 through m. This geometric sum is 2m−1. Since m<n, total copying costs less than 2n units. If no doubling has occurred, copying costs zero. Including the n new writes gives n≤T(n)<3n for every n≥1, where T(n) is the total work. Dividing by n gives amortised cost Θ(1) per append.
The growth rule matters. Adding just one slot when full would copy 0,1,2,…,n−1 records across the run, giving n(n+1)/2 work units including the writes. Doubling leaves room for more cheap appends after each increasingly expensive resize.
A resize still takes Θ(m) work units when it copies m records. The sequence bound describes how much work the backtest does overall. For a live market-data handler that appends on the path from receipt to processing, the resize is still part of that event's latency. The unit count gives neither elapsed time nor a deadline guarantee.
Dynamic Arrays and Amortized Analysis explains the resize setup and has a worked capacity trace in Exercise 1, starting from an empty array with one slot already allocated. The link opens a public preview. The full lesson requires membership.
