Efficiency of growing a dynamic array by a fixed c

Question

So when a dynamic array is doubled in size each time an element is added, I understand how the time complexity for expanding is O(n) n being the elements. What about if the the array is copied and moved to a new array that is only 1 size bigger when it is full? (instead of doubling) When we resize by some constant C, it the time complexity always O(n)?

Answer 1

If you grow by some fixed constant C, then no, the runtime will not be O(n). Instead, it will be Θ(n²).

To see this, think about what happens if you do a sequence of C consecutive operations. Of those operations, C - 1 of them will take time O(1) because space already exists. The last operation will take time O(n) because it needs to reallocate the array, add space, and copy everything over. Therefore, any sequence of C operations will take time O(n + c).

So now consider what happens if you perform a sequence of n operations. Break those operations up into blocks of size C; there will be n / C of them. The total work required to perform those operations will be

(c + c) + (2c + c) + (3c + c) + ... + (n + c)

= cn / c + (c + 2c + 3c + ... + nc / c)

= n + c(1 + 2 + 3 + ... + n / c)

= n + c(n/c)(n/c + 1)/2

= n + n(n/c + 1)/2

= n + n² / c + n / 2

= Θ(n²)

Contrast this with the math for when you double the array size whenever you need more space: the total work done is

1 + 2 + 4 + 8 + 16 + 32 + ... + n

= 1 + 2 + 4 + 8 + ... + 2^{log n}

= 2^{log n + 1} - 1

= 2n - 1

= Θ(n)

---

^{Transplanted from SO Documentation.}

Sums of powers of 2 — 1 + 2 + 4 + 8 + 16 + …

The sum

2⁰ + 2¹ + 2² + ... + 2^n-1

simplifies to 2ⁿ - 1. This explains why the maximum value that can be stored in an unsigned 32-bit integer is 2³² - 1.