2

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)
2

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.

  • I get it now, I guess I just got confused with the language and thought "half are copied once" is referring to numbers 1-8 in last line. Thanks Winston :) – Sourabh Feb 15 '17 at 6:28
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

  • 1
    I think the Op realizes that only log n copies happen. – CodesInChaos Feb 14 '17 at 19:54
  • @CodesInChaos: The amortization is the key concept here, and the fact that the expansion does not occur for every insertion. – Robert Harvey Feb 14 '17 at 19:55
  • I understand that it only reallocates when size is more than capacity, thus lg n. Book states If half the elements move once, quarter move twice and so on, say the half is red part of last line in the image, which is moved once from above, and quarter twice, which is copied from 3rd last line to 2nd last and then last line, isn't this counting movement of quarter items 3 times, once when we say half are copied and twice when quarter is copied, but in reality it moved only twice in total? – Sourabh Feb 14 '17 at 20:14
  • 1
    I don't think that's relevant. You take the amortized cost for the next n insertions each time you double the size of the array to 2n. How many times the items were previously moved is irrelevant. – Robert Harvey Feb 14 '17 at 20:21
  • @Sourabh, When it say that half of the element move once and a quarter move twice, the quarter isn't contained in the half. The quarter is in addition to the half. So overall, that accounts for three quarters of all the elements. – Winston Ewert Feb 14 '17 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.