Dynamic Array

A dynamic array is a data structure that has a fixed amount of space. Once all the spaces are filled and a new entry needs to be added, it will double in size.

It takes constant time or O(1) time to add an item to a dynamic array. It takes O(n) times to insert n items.

The sizing works by creating a new array and copying over information from the last array to the new array. Each time the array doubles, it will copy 1, 2, 4, … , n/4, n/2. This sum results in ~n. The total cost of insertion and copying from doubling will be 2n or O(n) times. so the (total cost) / (total cost for insertion) results in a O(1) cost per insertion.