Arrays vs Dynamic Arrays

Question

In Steven Skiena's The algorithm design manual Edition 2, he talks about dynamic arrays on page 67, which results in them having same Big-Oh as normal arrays. I don't understand how. This is what book states

Half the elements [in final array] were moved once, a quarter twice, and so on, so total movements M is given by

Isn't this counting some movements twice?

(The red part is copied from last array and blue is new inserted part)

For n insertions there are lg n array reallocations. So 1st item is copied lg n times, second one lg n - 1 times, next 2 lg n - 2 times, next 4 lg n - 3 times and so on.

I don't know how to solve this but what am I thinking wrong?

---

Here's my latex code, if someone wants edit it here

M = 1 \cdot lg_2 n + 1 \cdot (lg_2 n - 1) + 2 \cdot (lg_2 n - 2) + 4 \cdot (lg_2 n - 3)  
= \sum_{i = 1}^{lg_2 n - 1} 2^i \cdot (lg_2 n - i)

Answer 1

Let's imagine that I insert the first sixteen natural numbers:

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

The sequence goes like this:

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

• The numbers 9-16 are copied once.
• The numbers 5-8 are copies twice.
• The numbers 3-4 are copies three times.
• The number 2 is copies four times.
• The number 1 is copies five times.

Isn't this counting some movements twice?

No, the half and the quarter in the quote are distinct the values. The quarter isn't part of the half.

Answer 2

Dynamic arrays do not reallocate their size every time you do an insertion.

Rather, an insertion that requires the size of the array to increase will typically cause the array to double in size. The resulting cost of expansion is amortized over all of the insertions, which is to say that the cost is taken once over a geometrically increasing number of insertions, and not taken again for the original insertions.

Further Reading
Geometric Expansion and Amortized Cost