How many copies are needed to enlarge an array?
- by user10326
I am reading an analysis on dynamic arrays (from the Skiena's algorithm manual).
I.e. when we have an array structure and each time we are out of space we allocate a new array of double the size of the original.
It describes the waste that occurs when the array has to be resized.
It says that (n/2)+1 through n will be moved at most once or not at all. This is clear.
Then by describing that half the elements move once, a quarter of the elements twice, and so on, the
total number of movements M is given by:
This seems to me that it adds more copies than actually happen.
E.g.
if we have the following:
array of 1 element
+--+
|a |
+--+
double the array (2 elements)
+--++--+
|a ||b |
+--++--+
double the array (4 elements)
+--++--++--++--+
|a ||b ||c ||c |
+--++--++--++--+
double the array (8 elements)
+--++--++--++--++--++--++--++--+
|a ||b ||c ||c ||x ||x ||x ||x |
+--++--++--++--++--++--++--++--+
double the array (16 elements)
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+
|a ||b ||c ||c ||x ||x ||x ||x || || || || || || || || |
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+
We have the x element copied 4 times, c element copied 4 times, b element copied 4 times and a element copied 5 times so total is 4+4+4+5 = 17 copies/movements.
But according to formula we should have 1*(16/2)+2*(16/4)+3*(16/8)+4*(16/16)= 8+8+6+4=26 copies of elements for the enlargement of the array to 16 elements.
Is this some mistake or the aim of the formula is to provide a rough upper limit approximation? Or am I missunderstanding something here?
