Dynamic Arrays

Many languages have dynamic arrays, arrays that automatically resize, typically doubling whenever the array becomes full. Like static arrays, access is still $O(1)$, but doubling takes $O(n)$.

Doubling is rare enough that insertion (amortized) is still $O(n)$. The logic goes like this: if you have an array of $n$ elements, the most recent time the array doubled, $n/2$ elements were copied, the second most recent time, $n/4$ elements were copied, the third most recent time, $n/8$ elements were copied, and so on. So for $n$ total insertions, the total number of elements that have been copied is $n/2\; +\; n/4\; +\; n/8\; +\; ...\; 4\; +\; 2\; +\; 1$, which is less than $n$.

So on average, insertion is $O(n)$-- however, worst-case insertion is $O(n)$.