1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ What do you mean by random, do you mean that everytime the resizing happens, you increase the size by a random value or you mean any other choice other than doubling it everytime? $\endgroup$
    – Rinkesh P
    Mar 8, 2022 at 5:30
  • $\begingroup$ yeah increase by a random size as opposed to multiplying by a factor... $\endgroup$
    – xyf
    Mar 8, 2022 at 6:09
  • $\begingroup$ stackoverflow.com/questions/61377948/… check this post. $\endgroup$
    – Rinkesh P
    Mar 8, 2022 at 6:35
  • $\begingroup$ Doubling is actually not so much related to performance but to simplicity. It is mostly used in textbooks. Real-world implementations use different factors, e.g. Microsoft's implementation of the C++ STL uses 1.5x, as does .NET. For dictionaries, .NET uses 1.5x rounded up to the next prime number. Oracle's implementation of ArrayList[T] uses 1.25x. YARV uses 1.25x. Python uses 1.125x + 3 for smaller x and 1.125x + 6 for large x. 1.5x has some performance advantages over 2x. For a specific definition of "optimal" and an infinitely large array, the optimal value is actually the golden ratio. $\endgroup$ Mar 14, 2022 at 5:07

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.