fixed-increment growth
Growing a full array by adding the same number of slots each time, which leads to quadratic total copying.
In more detail
If an array grows by four slots at a time, it must copy everything every four appends, so n appends cost O(n^2) in copies. The course's trace shows 480 copies for 64 appends, against 63 for doubling. This is why real dynamic arrays grow by a factor, not a fixed amount.
Related terms
- 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.
- 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.
- quadratic time — Work that grows with the square of the input, written O(n^2): twice the items, four times the work.
Taught in
- Amortised Analysis: Why Append Is Cheap — Algorithms & Data Structures for Working Engineers