How many copies are needed to enlarge an array?

Posted by user10326 on Programmers See other posts from Programmers or by user10326
Published on 2011-11-11T06:29:17Z Indexed on 2014/06/04 9:38 UTC
Read the original article Hit count: 283

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:

enter image description here

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?

© Programmers or respective owner

Related posts about algorithms

Related posts about computer-science