What is total work of managing the dynamic array and why is it the same as for fixed array - O(n)

Question

I'm reading the chapter on dynamic arrays in The Algorithm Design Manual book. Here is the excerpt from the book:

Actually, we can efficiently enlarge arrays as we need them, through the miracle of dynamic arrays. 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 to the lower half of the new one, and returning the space used by the old array to the storage allocation system. The apparent waste in this procedure involves the recopying of the old contents on each expansion. How many times might an element have to be recopied after a total of n insertions? Well, the first inserted element will have been recopied when the array expands after the first, second, fourth, eighth, . . . insertions. It will take log2 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 nth elements will move at most once and might never have to move at all. If half the elements move once, a quarter of the elements twice, and so on, the total number of movements M is given by

Thus, each of the n elements move only two times on average, and the total work of managing the dynamic array is the same O(n) as it would have been if a single array of sufficient size had been allocated in advance!

The primary thing lost using dynamic arrays is the guarantee that each array access takes constant time in the worst case. Now all the queries will be fast, except for those relatively few queries triggering array doubling. What we get instead is a promise that the nth array access will be completed quickly enough that the total effort expended so far will still be O(n). Such amortized guarantees arise frequently in the analysis of data structures.]1

I don't understand why (n/2 + 1)st through nth will move at most once and might never have to move at all and total work of managing the dynamic array. Can someone please explain?

Also, why is the guarantee that each array access takes constant time in the worst case is lost with dynamic arrays?

Answer 1

All that matters is the equation you are quoting. Here is another way to see it. Suppose you have $n$ items. You push one item at a time to the end of an initially empty array. When the array reaches size $2^k$ for some $k<\log_2 n$, you reallocate the array to size $2^{k+1}$ and move all items between $0$ and $2^k-1$ to the new location. The total number of item moves is:

$$ M=1+2+2^2+\cdots+2^{\lfloor\log_2n\rfloor}=2^{\lfloor\log_2n\rfloor+1}-1\le2^{1+\log_2n}-1=2n-1 $$

If you fill the array in a random order, the total number of item moves is bounded by $2n$, too. In all, the time complexity of filling an array of size $n$ is $O(n)$, no matter whether the array is dynamic or not.

why is the guarantee that each array access takes constant time in the worst case is lost with dynamic arrays

When you push an item to the end of an array of size $2^k$, you have to double the array and possibly copy $2^k$ existing items to a new location. This is not a constant-time operation. With dynamic array, each single operation is not always constant. However, such non-constant operations are so rare that the total number of operations to fill a dynamic array can still be $O(n)$.