Re:Please grow your buffers exponentially
by Chinjut on Tuesday November 04, 2014 @01:38PM
(#8558219)
By "amortized O(1)", what's meant is essentially O(1) _per array element_; in other words, O(N) overall to reach a size of N. Note that this is when considering each reallocation to take time O(current length of array) [as one has to copy over all the current elements to the new space].
[ Parent
| on HN ]
Re:Please grow your buffers exponentially
by SerpentJoe on Tuesday November 04, 2014 @02:01PM
(#8558364)
Ah yeah, I was double wrong. I see now that N insertions require a maximum of 2N-3 copy operations (with a growth factor of 2), so O(1) amortized. Thanks!