Reasoning behind specifically doubling the array size upon reallocation

Question

I am trying to understand the actual reasoning behind creating a new dynamic array of double the size of the original array once it gets full as opposed to any reasonably random number (not too small that buffer is getting filled up too often neither it being too large that half the indices are empty).

Apparently, it has to do with performance but can't get my head around it.

For instance:

// original array of size 3 has been allocated which gets filled up at some point

int *arr;
arr = new int[3];

// arr at some point: {1,2,3}

// now there's a request to add a 4 into the array but since arr is full, you delete arr, create a new arr with size 7 instead of 6

newArr: {1,2,3,4,0,0,0}; // assuming you init'd the array to 0

I observe the following:

• you copy the elements from the original array -> O(N)
• you append 4 to the corresponding index -> O(1)

and that's going to be the same if you were say double the array size as well except you'd be reallocating more frequently.

So where's the difference in performance between reallocating double the size vs any reasonably random size?

Edit:

My incomplete understanding:

Sum of power of 2 = Σ2^(N-1)

N=2 -> Σ2^(1)  = 2^0 + 2^1 = 1 + 2 = 3 (+1) = 4

Therefore:

1 + 2 + 4 + 8 + ... + Σ2^(N-1) == 3/2 * 2^N ≈ O(N)

And, with M number of insertions:

O(N) / O(M) = O(1)

Is ny understanding somewhat correct? If so, how would the equation be different for increasing the array size by a constant k (say 100) factor as opposed to doubling?

Answer 1

Lets analyze both the cases.

Assume the growth factor to be $k$.

Case 1: Increasing the size by a constant factor. The amount of work done to resize the array $m$ times would be

$(1)+(1+k)+(1+2k)+(1+3k)....+(1+mk)$. This is an arithmetic progression whose sum is given by $(m/2)*(2+(m-1)*k)$, so of the order $O(m^2)$.

Case 2: Increasing the size exponentially. The amount of work done to resize the array $m$ times would be

$1+k+k^2+k^3....+k^m$. This is a geometric progression whose sum is given by $(k^m - 1)/(k-1)$, so of the order $O(k^m)$.

Upon looking at these expressions directly, it's easy to say that growing the array exponentially would drag the performance down much more than what growing it linearly would do. And while that is true, the fact is that we won't be growing the array the same number of times in both the cases(unless you somehow manage infinite memory and input).

Lets assume now that you have $n$ elements to be stored.

Case 1: $1+mk=n$ --> $m=(n-1)/k$

Case 2: $k^m=n$ --> $m=log(n)/log(k)$

Clearly When increasing the size exponentially, you in turn have to perform the resizing very few times as compared to growing it linearly. Dynamic memory allocation itself has its associated costs, which you can read upon from here. As to why doubling is used, it mostly makes the calculations easier. There are other options too and this post has some decent discussions on those. A major part of the performance impact would be the frequency of the resize operations.