4 ms·
O(1), or O(log N)? Small difference but I was just having this argument yesterday. Each reallocation takes O(1) time (we assume), and you need O(log N) realloca
by SerpentJoe 12y ago
O(1), or O(log N)? Small difference but I was just having this argument yesterday. Each reallocation takes O(1) time (we assume), and you need O(log N) reallocations to grow by a cumulative factor of N.
- Chinjut 12y agoBy "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].
- SerpentJoe 12y agoAh 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!