# How many copies are needed to enlarge an array?

I am reading an analysis on dynamic arrays (from the Skiena's algorithm manual).
I.e. when we have an array structure and each time we are out of space we allocate a new array of double the size of the original.

It describes the waste that occurs when the array has to be resized.
It says that (n/2)+1 through n will be moved at most once or not at all. This is clear.
Then by describing that half the elements move once, a quarter of the elements twice, and so on, the total number of movements M is given by: This seems to me that it adds more copies than actually happen.

E.g.

if we have the following:

``````array of 1 element
+--+
|a |
+--+

double the array (2 elements)
+--++--+
|a ||b |
+--++--+

double the array (4 elements)
+--++--++--++--+
|a ||b ||c ||c |
+--++--++--++--+

double the array (8 elements)
+--++--++--++--++--++--++--++--+
|a ||b ||c ||c ||x ||x ||x ||x |
+--++--++--++--++--++--++--++--+

double the array (16 elements)
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+
|a ||b ||c ||c ||x ||x ||x ||x ||  ||  ||  ||  ||  ||  ||  ||  |
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+
``````

We have the x element copied 4 times, c element copied 4 times, b element copied 4 times and a element copied 5 times so total is 4+4+4+5 = 17 copies/movements.

But according to formula we should have 1*(16/2)+2*(16/4)+3*(16/8)+4*(16/16)= 8+8+6+4=26 copies of elements for the enlargement of the array to 16 elements.

Is this some mistake or the aim of the formula is to provide a rough upper limit approximation? Or am I missunderstanding something here?

• Another factor: in the real-world, the empty allocated elements would be zeroed out (in a high-level language like Java or C#). This entails a write (but not a read), that seems to cost half as much as a copy. – dbkk Nov 11 '11 at 7:50
• Your sums aren't correct; `b` is copied 3 times, each `c` twice, and each `x` once. 15 copies. – Donal Fellows Nov 11 '11 at 10:32

Firstly, b is moved 3 times and a is moved 4 times, which gives a total of 4 + 4 + 3 + 4 = 15 copies.

I think the formula should be filled in with n=8: 1*(8/2) (x is copied once) + 2*(8/4) (c is copied twice) + 3*(8/8) (b is copied thrice) = 11. In other words, the formula seems to be missing a "+ log2 n + 1" term in addition to the sum itself.

What would seem to me to be a much more natural way to count the number of moves is to count the number of moved elements per copy:

sum from i = 1 to i = ceiling(log2 n): 2i-1

In your case, n = 16, so ceiling(log2 16) = 4 and the sum above is: 20+21+22+23 = 1 + 2 + 4 + 8 = 15.

I'll see if I can find this Skiena's algorithm manual to see if I got it correct.

Update: I found the part in Skiena's algorithm manual. It does seem like there there is a term missing in the sum he uses there. However, the conclusion is correct:

M = sum from i = 1 to i = ceiling(log2 n): 2i-1 = sum from i = 0 to i = ceiling(log2 n) - 1: 2i = 2ceiling(log2 n) - 1 + 1 <= (2log2 n + 1 - 1 + 1) = 2 * n

(I wish I could format these formulas in a nicer way for you)

The main point of this paragraph seems to be to give an example of amortized analysis. Methods such as the potential method would make a better (less ad hoc) argument why dynamic arrays perform very well, but this method is somewhat advanced.

If you are convinced there is an error in this book, you could consider contacting the author about this (in a constructive way of course - the book has a lot of pages, and it's hard to get every last thing correct, and there's always a chance that the book is right and we both got it wrong). I haven't found this particular one on the errata.

• I formatted the formulas a bit :-) – Péter Török Nov 11 '11 at 11:28
• Thank you, it looks much nicer now - I'm used to LaTeX formatting, and I don't think that's possible on Programmers.SE. – Alex ten Brink Nov 11 '11 at 11:39
• @Alex:+1 thank you for this.I was wondering why do you think that in the OP the n should be 8 and not 16.I didn't get that. – user10326 Nov 11 '11 at 14:54
• Because then the i*n/2^i terms make sense: if i = 1, then you talk about 1 * n/2, which would correspond to half the input being copied once. In his example, there are four x positions that get copied once, and 8/2=4, so n=8 would make more sense. If n=16, then 16/2=8 elements would supposedly be copied once, which simply doesn't match the example. – Alex ten Brink Nov 11 '11 at 16:26

At the lower block count levels, its unlikely that a memory allocation actually occurs. Memory managers deal in blocks of memory and routinely allocate larger blocks of memory than the allocation request acutually asked for.

Likewise, the implementation of an array class is likely to round up allocations to allow for a few additional elements.

EDIT:

On further reflection, the actual copies are unlikely to occur as you describe them either. Processors usually have a block copy command and would use a single assmbler instruction to copy the array data as a single block of memory to the new address.

• Sorry, how is this related to my question? – user10326 Nov 11 '11 at 8:38
• Well if an allocation does not need to occur, then there is no need to copy the array elements to the new memory space. – Michael Shaw Nov 11 '11 at 8:40
• But I am asking about the formula. – user10326 Nov 11 '11 at 8:59
• Fair enough, its a mathematical question and I am giving programming answers on a programming site... ;) – Michael Shaw Nov 11 '11 at 9:17

I believe the formula given in the book is simply incorrect. The `i` multiplier has to be dropped from the formula to fix it.

Let's take the asker's example and call the array of 1 element array-1, the array of 2 elements -- `array-2`, the array of 4 elements -- `array-4`, and so on.

So, accordingly to the book, for this particular example the number of copyings is governed by the following formula:

``````
M = 1⋅8 + 2⋅4 + 3⋅2 + 4⋅1
``````

The first term of the sum `1⋅8` is for copying `array-8's` items into `array-16`.

We copy the `array-4's` items `(a, b, c, c)` twice. Once from the `array-4` to `array-8`. And then when copying `array-8's` items to `array-16` we copy `(a, b, c, c)` items for the second time. Accordingly to the book, hence the second term: `2⋅4`.

But now notice that the `1⋅8` term already takes into account copying of `(a, b, c, c)` items from `array-8` to `array-16`. Consequently the `2⋅4` term must not include the `2` multiplier.

The same logic applies to all the other terms. And so multiplying by `i` is a mistake.

• would you mind explaining more on what it does and why do you recommend it as answering the question asked? "Link-only answers" are not quite welcome at Stack Exchange – gnat Jun 4 '14 at 9:22
• Sure. I will copy my answer from cs.stackexchange. The problem is though that programmers.stackexchange doesn't allow proper math formulas formatting. – Nik Jun 4 '14 at 9:24
• per my reading, the formulas in your answer at CS can be reasonably approximated using code formatting with backticks: `M=1⋅8+2⋅4+3⋅2+4⋅1` etc – gnat Jun 4 '14 at 9:26