4 ms·
The amortized cost of prepend (unshift in ruby) is O(1) (since Ruby 2). Of course that means at some point you'll get O(n) prepend. [1] https://stackoverflow.
by bhrgunatha 8y ago
The amortized cost of prepend (unshift in ruby) is O(1) (since Ruby 2). Of course that means at some point you'll get O(n) prepend.
[1] https://stackoverflow.com/questions/8353026/what-is-the-run-time-of-shift-unshift-in-a-ruby-array https://stackoverflow.com/questions/8353026/what-is-the-run-...
- userbinator 8y agoGetting amortised O(1) prepend is interesting because it's just like append, except you "center" or "right-justify" (if you don't care about O(1) append) the array in the allocated space, and exponentially reallocate when full as with append.