Efficiency of growing a dynamic array by a fixed c

2020-06-18 10:31发布

问题:

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)?

回答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