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

Taught in

References