The number of movements in a dynamic array

Question

A dynamic array is an array that doubles its size when an element is added to an already full array, copying existing elements to a new location in more detail here . It is understood that there will be ceil(log(n)) bulk copy operations.

In the tutorial, I saw how the number of movements M calculated in this way:

M=sum for {i=1} to {ceil(log(n))} of i*n/{2^i} with the argument that "half of the elements move once, a quarter of the elements twice" ...

But I thought that for each volume copy operation, the number of copied / moved elements is actually n/2^i , since each mass operation is started by reaching and exceeding the element 2^i th , so the number of movements

M=sum for {i=1} to {ceil(log(n))} of n/{2^i} (for n = 8 this is the correct formula).

Who is right and what is not in another argument?

Answer 1

Both versions: O (n) , so there is not much difference.

In the tutorial version, the initial recording of each element is performed as a move operation, but the very first element that will move ceil(log(n)) times is not taken into account. In addition, they are equivalent, i.e.

 (sum for {i=1} to {ceil(log(n))} of i*n/{2^i}) - (n - 1) + ceil(log(n)) == sum for {i=1} to {ceil(log(n))} of n/{2^i} 

when n is a power of 2. Both are disabled by different amounts, when n not a power of 2.