4 ms·
I thought generally dynamic arrays were allocated more memory than the last allocation every time an appending happens, so that future appends are faster. Might
by jimmaswell 13y ago
I thought generally dynamic arrays were allocated more memory than the last allocation every time an appending happens, so that future appends are faster. Might've been the vector class from C++ I heard that about.
- kbolino 13y agoIndeed, 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.
- deleted 13y ago[deleted]