How is this formula regarding dynamic array resizing reached?

Question

I have also posted this to mathematics.stackexchange and theoreticalcomputerscience.stackexchange. But I am not certain whether it is actually more suitable for this forum.

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.

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 doublings until the array gets to have n positions. However, most elements do not suffer much upheaval. Indeed, the st through nth 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 by i.

Answer 1

It stands for the number of copies. Let's work out a simple example. Take insertions in following order

[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

Element 16 doubles the array (since it became greater than 2^4).

Lets compute copies:

15,14,13,12,11,10,9,8 were copied just once (i=1) * (n/2^i)
7,6,5,4               were copied twice (i=2)
3,2                   were copied three times (i=3)
1                     was copied 4 times (i=4)
0                     was copied 5 times (i=5)

Thus I suppose that, for the upper bound, it should be ceil(log n) in the sum limit and ceil(n/2^i) in the sum, but anyway this should answer the question where does the i come from.

Answer 2

It is saying that n/2 elements are copied at most once (as you rightly inferred). Further, n/4 elements are copied twice. n/8 elements are copied 3 and so on.