How is this formula for dynamic array reached?

Question

I am reading through Skiena's "The Algorithm Design Manual". He analyses the number of copy operations performed in a dynamic array.

"Suppose we start with an array of size 1, and double its size from $m$ to $2m$ each time we run out of space. This doubling process involves allocating a new contiguous array of size $2m$, copying the contents of the old array into the lower half of the new one. The apparent waste is in the recopying of the old contents, on each expansion."

Skiena then asks:

"How many times might an element have to be recopied after a total of $n$ insertions?".

He then gives a formula for calculating the total number of movements $M$, for $n$ insertions, which is

$$\mathbf{M}=\sum_{i=1}^{\log n} i\cdot\frac{n}{2^i}.$$

His explanation is:

"Well, the first inserted element will have been recopied when the array expands after the first, second, fourth, eighth, ...insertions. It will take $\log_{2}n$ doublings until the array gets to have n positions. However, most elements do not suffer much upheaval. Indeed, the $(n/2 + 1)$st through $n$th elements will move at most once and might never have to move at all."

But I really don't understand how he draws the formula from that. Can anyone help me understand how he reaches it? Mainly what I can't understand is why he is multiplying $\frac{n}{2^i}$ by $i$.

Answer 1

Let's look at the moment just after we copy the array to insert element $2^k + 1$, so we're doubling the array size from $2^k$ to $2^{k+1}$. There are $n = 2^k$ elements in the array at this moment.

The first term in the sum is $1 \cdot n/2$, representing the fact that $n/2$ elements (namely, elements $(n/2+1), \ldots, n$) have been copied exactly once (just now!).

The next term is $2 \cdot n/4$. The previous $n/4$ elements - that is, elements $(n/4) + 1, \ldots, n/2$ - will have been copied exactly twice, once just now and once when we expanded the array from size $n/2$ to $n$.

The next term is $3 \cdot n/8$. The previous $n/8$ elements will have been copied three times: now, at the last expansion and at the second-to-last expansion when we expanded from size $n/4$ to $n/2$. You can probably see where this is going by now.

The thing to remember is that each element gets copied every time the array expands after the element in question has been inserted, and the copies happen every time the size exceeds a power of two.

Answer 2

Mainly what I can't understand is why he is multiplying $\frac{n}{2^i}$ by $i$.

I believe this is a mistake in the book. Let's take a look at an example (taken from https://softwareengineering.stackexchange.com/questions/119151/how-many-copies-are-needed-to-enlarge-an-array)

Array of 1 element.
Let's call it array-1.
+--+
|a |
+--+

Double the array (2 elements).
Let's call it array-2.
+--++--+  
|a ||b |  
+--++--+  

Double the array (4 elements).
array-4.
+--++--++--++--+  
|a ||b ||c ||c |  
+--++--++--++--+  

Double the array (8 elements).
array-8.
+--++--++--++--++--++--++--++--+    
|a ||b ||c ||c ||d ||d ||d ||d |  
+--++--++--++--++--++--++--++--+    

Double the array (16 elements).
array-16.
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+    
|a ||b ||c ||c ||d ||d ||d ||d ||  ||  ||  ||  ||  ||  ||  ||  |   
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+   

So, accordingly to the book number of copyings is governed by the following formula: $M = 1 \cdot 8 + 2 \cdot 4 + 3 \cdot 2 + 4 \cdot 1$

The first term of the sum $1 \cdot 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 \cdot 4$.

But now notice that the $1 \cdot 8$ term already takes into account copying of (a, b, c, c) items from array-8 to array-16. Consequently the $2 \cdot 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.