Aggregate Method and the Dynamic Array
What This Concept Is
The aggregate method bounds actual total work directly and divides by sequence length. For an append-only array doubling from capacities 1,2,4,..., copied elements form a geometric sum. Fixed-increment growth produces a different sum and therefore a different amortized cost.
Why It Matters Here
The argument must work at arbitrary prefixes, including immediately after a resize. Quoting the cost only at full capacities can hide the expensive prefix a user actually encounters.
Concrete Examples
In the lab, append writes the new element once and, when full, copies the
old capacity. For n>=1, total work is n plus the copied capacities below n:
1+2+4+...+2^j < 2n. Therefore total work is less than 3n. At n=9,
copies total 1+2+4+8=15 and writes total 9, yielding 24.
Capacity after a positive append is at least n and less than 2n except that the loose bound may be written at most 2n. Peak resize memory includes both old and new buffers while copying; final capacity alone understates temporary storage. The lab is a teaching model, not an assertion of a particular runtime's growth factor or allocator cost.
With fixed increment c, capacities grow c,2c,3c,... and cumulative copies form an arithmetic sum, Θ(n²/c) for fixed c and sufficiently large n. Charging a constant per append cannot pay for all such copies.
Deletion extension. Growing at full and shrinking as soon as half full can oscillate: near the threshold, alternating append/delete repeatedly copies Θ(n) elements. Separate thresholds, such as grow at full and shrink at one-quarter full to half capacity, introduce hysteresis. Derive that new contract separately; the reference intentionally exposes append-only operations.
Common Confusion / Misconceptions
A resize's copy count is the old number of live elements, not the new capacity. Allocation/initialization may add work but must not be mislabeled as copied old elements. Geometric growth is not a guarantee against a single long pause. Shrinking needs its own sequence analysis.
How To Use It
Write exact costs for prefixes around powers of two, derive the geometric sum and include peak live allocation. Compare counters with the proof. For a shrink extension, exhibit the oscillation sequence before choosing hysteresis and proving the revised aggregate or potential bound.
Check Yourself
Why is n=9 more revealing than n=8 for resize spikes? What causes quadratic work under fixed increments? Why does a two-threshold policy help deletion?
Mini Drill or Application
At n=17, count writes and copies. Feedback: 17 writes plus 31 copies = 48. Final capacity is 32, and the resize briefly holds old capacity 16 plus new capacity 32.
Read This Only If Stuck
CLRS: dynamic tables. Match the source growth/shrink and initial-capacity conventions to the version you implement.