doubling strategy

Growing a full dynamic array by multiplying its capacity by a constant factor, typically two, rather than adding a fixed number of slots.

In more detail

With doubling, n appends trigger copies totalling fewer than 2n element moves, so each append is O(1) amortised. The course's trace shows doubling copying 15 elements for 16 appends where a fixed increment of four copies 24. Real implementations such as CPython use a smaller factor, but any constant factor above one gives the same bound.

Related terms

Taught in

References