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
- fixed-increment growth — Growing a full array by adding the same number of slots each time, which leads to quadratic total copying.
- dynamic array — An array that grows on demand by allocating a larger block and copying the existing items across when it runs out of room.
- amortised analysis — Measuring the average cost per operation over a long sequence of operations, so rare expensive steps are spread across many cheap ones.
Taught in
- Why Complexity Matters In Production — Algorithms & Data Structures for Working Engineers
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Amortised Analysis: Why Append Is Cheap — Algorithms & Data Structures for Working Engineers
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers
- Bloom Filters: Membership Without The Data — Algorithms & Data Structures for Working Engineers
- Representing A Graph: Matrix Or Adjacency List — Algorithms & Data Structures for Working Engineers