display | more...

Far too often, I see code like this, used to append an element to an array: (in C-like pseudocode)

```...
if (num_elements >= array_size)
{
temp_array = allocate(array_size+1)
copy_elements(temp_array, array, array_size)
destroy(array)
array_size = array_size+1
array = temp_array
}
array[num_elements] = element_to_append;
num_elements = num_elements+1
```

Well, as you add elements, the amount of (potentially) wasted space grows with the square of the number of elements in the array. If you start with an array of length 1, adding a second element will throw away the length-1 array. Adding a third element will throw away the length-2 array. Adding a fourth element will throw away the length-3 array. So for N elements, the amount of wasted space ends up being 1+2+3+....+(N-1), or O(N2). (see Gaussian Formula for more on that one.)

What can you do to avoid this (potentially) huge waste of space? Instead of increasing the allocated space by 1 every time, double the allocated space! So the code changes to something like:

```...
if (num_elements >= array_size)
{
temp_array = allocate(array_size*2)
copy_elements(temp_array, array, array_size)
destroy(array)
array_size = array_size*2
array = temp_array
}
array[num_elements] = element_to_append;
num_elements = num_elements+1
```

And, pray tell, how is that more space-efficient?

Well, simple! Again, starting with the one element array, adding a second element allocates a 2-element array, and throws away the 1-element array. Adding a third element, throws away the 2-element array, and allocates a 4-element array. Adding a fourth element is where the magic begins; no array is thrown away, and no new space is allocated. Adding a fifth element throws away the 4-element array, and allocates an 8-element one, but THAT array will not be thrown away until another four elements are added, and the array allocated then will survive another 8 elements. And so on, and so forth; The wasted space for adding N elements is 1+2+4+8+...+log2N, or O(N).

Right, so anyway, DOUBLE!