136. For an array-backed stack, compare growing by doubling with growing by a constant amount.
MediumStacks
Technical
Show model answer
With doubling, a resize copies the current n elements into a 2n array. Over n pushes the copies total 1 + 2 + 4 + ... < 2n, so push is O(1) amortised even though a single push can cost O(n). Unused capacity is at most about n slots.
Growing by a constant c copies after every c pushes, giving c + 2c + 3c + ... which is about n² / (2c) total work, or O(n) amortised per push. So geometric growth is the standard choice; to shrink safely, halve only when the array is a quarter full to avoid thrashing at the boundary.
What interviewers listen for
- Doubling: O(1) amortised push. Constant growth: O(n) amortised push.