How many copies are needed to enlarge an array?

Question

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?

Answer 1

Firstly, b is moved 3 times and a is moved 4 times, which gives a total of 4 + 4 + 3 + 4 = 15 copies.

I think the formula should be filled in with n=8: 1*(8/2) (x is copied once) + 2*(8/4) (c is copied twice) + 3*(8/8) (b is copied thrice) = 11. In other words, the formula seems to be missing a "+ log₂ n + 1" term in addition to the sum itself.

What would seem to me to be a much more natural way to count the number of moves is to count the number of moved elements per copy:

sum from i = 1 to i = ceiling(log₂ n): 2^i-1

In your case, n = 16, so ceiling(log₂ 16) = 4 and the sum above is: 2⁰+2¹+2²+2³ = 1 + 2 + 4 + 8 = 15.

I'll see if I can find this Skiena's algorithm manual to see if I got it correct.

Update: I found the part in Skiena's algorithm manual. It does seem like there there is a term missing in the sum he uses there. However, the conclusion is correct:

M = sum from i = 1 to i = ceiling(log₂ n): 2^i-1 = sum from i = 0 to i = ceiling(log₂ n) - 1: 2ⁱ = 2^{ceiling(log₂ n) - 1 + 1} <= (2^{log₂ n + 1 - 1 + 1}) = 2 * n

(I wish I could format these formulas in a nicer way for you)

The main point of this paragraph seems to be to give an example of amortized analysis. Methods such as the potential method would make a better (less ad hoc) argument why dynamic arrays perform very well, but this method is somewhat advanced.

If you are convinced there is an error in this book, you could consider contacting the author about this (in a constructive way of course - the book has a lot of pages, and it's hard to get every last thing correct, and there's always a chance that the book is right and we both got it wrong). I haven't found this particular one on the errata.

Answer 2

At the lower block count levels, its unlikely that a memory allocation actually occurs. Memory managers deal in blocks of memory and routinely allocate larger blocks of memory than the allocation request acutually asked for.

Likewise, the implementation of an array class is likely to round up allocations to allow for a few additional elements.

EDIT:

On further reflection, the actual copies are unlikely to occur as you describe them either. Processors usually have a block copy command and would use a single assmbler instruction to copy the array data as a single block of memory to the new address.

Answer 3

I believe the formula given in the book is simply incorrect. The i multiplier has to be dropped from the formula to fix it.

Let's take the asker's example and call the array of 1 element array-1, the array of 2 elements -- array-2, the array of 4 elements -- array-4, and so on.

So, accordingly to the book, for this particular example the number of copyings is governed by the following formula:

M = 1⋅8 + 2⋅4 + 3⋅2 + 4⋅1

The first term of the sum 1⋅8 is for copying array-8's items into array-16.

We copy the array-4's items (a, b, c, c) twice. Once from the array-4 to array-8. And then when copying array-8's items to array-16 we copy (a, b, c, c) items for the second time. Accordingly to the book, hence the second term: 2⋅4.

But now notice that the 1⋅8 term already takes into account copying of (a, b, c, c) items from array-8 to array-16. Consequently the 2⋅4 term must not include the 2 multiplier.

The same logic applies to all the other terms. And so multiplying by i is a mistake.