Menu
Is the runtime complexity defined by the JS standard on common Array functions like push, pop, shift, slice or splice? Esp. I'm interested in removing and inserting entries at random positions. If the complexity is not defined, what can I expect, e.g. in V8?
(This question was inspired by this. Also, this benchmark, posted here, also makes me curious, but maybe that is some unrelated phenomena.)
(A very related question is here. However, one of the comments on the accepted answer says that it is wrong now. Also, the accepted answer does not have any reference that the standard really defines it that way.).
796
The time complexity of Array. prototype. find is O(n) (with n being the array's length), and it's fair to assume that it will remain that way. Generally speaking, it's often impossible for engines to improve the complexity class of an operation.
shift() methods which are used to remove an element from the end and beginning of an array respectively, work similarly. Array. pop() is O(1) while Array. shift() is O(n).
The time complexity of the filter function is O(n) as well. At this moment, the total time complexity is O(2n). The last step is reduce function. We apply the result of the filter function to reduce function.
The ECMA specification does not specify a bounding complexity, however, you can derive one from the specification's algorithms.
push is O(1), however, in practice it will encounter an O(N) copy costs at engine defined boundaries as the slot array needs to be reallocated. These boundaries are typically logarithmic.
pop is O(1) with a similar caveat to push but the O(N) copy is rarely encountered as it is often folded into garbage collection (e.g. a copying collector could only copy the used part of an array).
shift is at worst O(N) however it can, in specially cases, be implemented as O(1) at the cost of slowing down indexing so your mileage may vary.
slice is O(N) where N is end - start. Not a tremendous amount of optimization opportunity here without significantly slowing down writes to both arrays.
splice is, worst case, O(N). There are array storage techniques that divide N by a constant but they significantly slow down indexing. If an engine uses such techniques you might notice unusually slow operations as it switches between storage techniques triggered by access pattern changes.
One you didn't mention, is sort. It is, in the average case, O(N log N). However, depending on the algorithm chosen by the engine, you could get O(N^2) in some cases. For example, if the engine uses QuickSort (even with an late out to InsertionSort), it has well-known N^2 cases. This could be a source of DoS for your application. If this is a concern either limit the size of the arrays you sort (maybe merging the sub-arrays) or bail-out to HeapSort.
80
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
