Recently, I encountered a question about a data structure similar to a dynamic array.  When you push a new element to a dynamic array (e.g. std::vector in C++ and ArrayList in java) and if it doesn’t have anymore storage, a reallocation will occur.

I remember last time when I was 2nd year student, a very 1st book I read about game engine programming told me how to dynamically increase the storage of dynamic array by increasing its size by a fixed amount (example: increase storage size by 5 elements, hence you are allowed to push 5 more elements before next resize, and so on).

I kept adhering to this implementation for a while until at some point, I realized it is not the most efficient way of resizing the array. Actually I was told it is that way, and hadn’t really thought of why. So let’s analyse its performance complexity today.

Average time complexity of fixed size increment

Average of n pushed, in which n=5*k+1:

  • First push (resize occurs): O(5)
  • Second push: O(1)
  • …
  • Sixth push: O(5+5) = O(10)
  • …
  • Eleventh push: O(10+5) = O(15)
  • …
  • n-th push: O(n/5 * 5 + 5) = O(n)

Total time of n pushes:

  • O(n) + O(5 + 2*5 + 3*5 + … + n/5*5) = O(n) + O(5 * (1 + 2 + 3 + … + n/5))
  • = O(n) + O((1 + n/5) * n / 2) = O(n) + O((5 + n) * n / 10)
  • = O(n^2)

Average time of n pushes:

  • O(n^2) / n = O(n)

The more efficient resize strategy

The more efficient way in term of average time complexity of resizing array is double its storage size every time a reallocation is required. After n pushes, assuming the array’s storage size is 2^k. This implies 2^(k-1) ≤ n ≤ 2^k. The average time of n pushes is:

  • O(n + 1 + 2 + 4 + … + 2^k) / n
  • = O(n + 2^(k+1)) / n
  • = (n + 4 * 2^(k-1)) / n ≤ O(n + 4 * n) / n = O(1)

Note: The cost of resizing the storage to become 2^k size is O(2^k) since you have to allocate 2^k new buckets then copy the previous 2^(k-1) elements of the array to the new buckets. Some people might say the cost is actually O(2^(k-1)) since only the copying of previous 2^(k-1) elements need to be accounted. Nevertheless, in that case, the time complexity of n pushes is O(n + 2 * n) which is still equivalent to O(n).

Furthermore, even though the memory complexity of this strategy is still O(n), it tends to waste more space the bigger the array becomes.

Alternative resize strategy

Recently, I read some articles and found out that there is another strategy for resizing the array without copying its old content to the new allocation. That is using an array of fixed size blocks (it is the way std::deque is typically implemented). However, the array elements won’t necessary be adjacent to each other in memory anymore.