Indeed, and most implementations use exponential scaling when allocating a new array. So although your worst-case insertion time is O(n) from copying the entir

Indeed, and most implementations use exponential scaling when allocating a new array. So although your worst-case insertion time is O(n) from copying the entire array, over a sequence of n operations, this only happens log n times, so you have O(log n) amortized time. Edit: All the references to "constant amortized time" lead me to reevaluate this claim, and it's not correct. Let's say you start with an initial capacity of 2, and double the capacity when necessary. Then the cost of adding n elements to the list will be n + the sum of 2^i from i=1 to i=log(n), which is n + 2(n - 1) or O(n). Over n operations, that's O(1) amortized.