Reference for Dynamic Arrays

Question

I'm looking for a reference for the fact that dynamic arrays have random access in constant time and inserting or deleting an element at the end can be done in constant amortized time. What would be a good reference for this?

Answer 1

This is probably the most basic interesting example of amortized analysis, so if you consider any text that covers amortized analysis you will find this. The so-called CLRS algorithms book for example has it. However buying a book to understand dynamic arrays may be a bit overkill unless you want to learn additional things.

Anyway, the idea behind dynamic arrays is if you insert at the end and fill up the array, then you allocate a new array of double the size, move over all the elements into the first half of the new array, and then delete the first array. Also, if the number of elements filled in your array ever becomes less than $1/4$ the size of the array, you create a new array of half the size, copy over all the elements and then delete the old array.

The constants $2$ and $1/4$ and $1/2$ can be played with. The point is, with these constants, at any given time, the amount of memory you are using is no more than $4$ times the number of elements filled, and furthermore, when you reach the point where you grow the array, you have done at least $n/2$ operations where $n$ is the size of the existing array, so the "cost" when you double the size of the array is that you copy $n$ elements, and since you've done at least $n/2$ previous operations, you can say that the charge of $n$ can be distributed out to be an average charge of $2$ to each one of your $n/2$ previous operations. So that "average" is called amortized $O(1)$ time. Similar argument applies when you have to shrink the array.