how to increase the size of an array

short answer: "double it"

long answer:

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

This is BAD BAD BAD! Why?

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(N²). (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+...+log₂N, or O(N).

Right, so anyway, DOUBLE!

Addendum:

Gorgonzola informs me that it has been determined experimentally that a factor of 1.5 is more optimal than 2, as a factor for increasing the size of an array, when both space and time are factors. Well, the Big-O analysis works out the same, no matter what factor you use (as long as it's greater than 1, of course), apparently Bjarne Stroustrup likes the factor of 1.5 better than 2, so who am I to argue?