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 byThus, 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.]1I 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?
What is total work of managing the dynamic array and why is it the same as for fixed array - O(n)
data structures;arrays
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 arraysWhen 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)$.