JavaScript runtime complexity of Array functions

Question

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.).

chuckj · Accepted Answer · 2014-03-25T03:29:27.390

174

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.

edited Mar 25 '14 at 03:29

answered Mar 24 '14 at 16:58

chuckj

27,773
7
53
49

1

This is great, but without a source specific to javascript, it's hard to verify. For instance, I know that sort can be O(NlogN), but is it in every language? No. (Also, what about filter, reverse, etc?) – David Manheim Mar 26 '14 at 18:20
2

These are hard to verify but you can rely on them being no worse complexity than the algorithm in the spec. As for `filter` and `reverse` they are _O(N)_. – chuckj Mar 26 '14 at 23:05
Do you have some ideas for Array.filter? – carmelolg Jul 20 '16 at 12:17
Worse case of _O(N)_ as discussed in the previous comment. – chuckj Jul 25 '16 at 17:47
7

What about `concat`? – Elias Zamaria Jun 14 '17 at 03:01
7

Please mention `unshift()`, I assume that's O(n) as well. – Alexander Mills Jun 04 '18 at 01:10
1

It's worth mentioning that this is correct even for [sparse arrays](https://www.oreilly.com/library/view/javascript-the-definitive/9781449393854/ch07s03.html). Empty elements are included in N. – subdavis May 24 '19 at 17:16
3

concat and unshift are almost certainly O(n) – Whatabrain Aug 16 '20 at 01:55

Sarwar Sateer · Answer 2 · 2021-03-14T13:12:15.627

14

in very simple words

push -> O(1)

pop -> O(1)

shift -> O(N)

slice -> O(N)

splice -> O(N)

Here is a complete explanation about time complexity of Arrays in JavaScript.

edited Mar 14 '21 at 13:12

answered Mar 04 '21 at 13:21

Sarwar Sateer

395
3
16

1

Yes, exactly! `Array.prototype.splice` is a universal multifunctional tool, and its complexity depends on what is done with it. For example, it can remove and/or add the last element (as push or pop), then complexity will be O(1); if it performs same as shift /unshift, its complexity will be O(n). Also other, "middle" situations are possible. – Roman Karagodin Mar 14 '21 at 12:58
1

Yeah, So we can say, in the worst case, it's still O(n). – Sarwar Sateer Mar 14 '21 at 13:14
That article hypothesizes a lot but doesn't cite the standard (which also doesn't specify complexities) or any specific engine. Just because it would be smart to implement things that way, doesn't mean any specific implementation is forced to do so. – General Grievance Mar 02 '23 at 13:31

score 3 · Answer 3 · answered Aug 11 '19 at 09:03

3

Just a side note, it is possible to implement shift / unshift, push / pop methods in O(1) using RingBuffer (i.o.w CircularQueue / CircularBuffer) data structure. It would be O(1) for worst case whenever the circular buffer is not required to grow. Did anyone actually measure performance of these operations? It's always better know rather than to guess...

answered Aug 11 '19 at 09:03

Lu4

14,873
15
79
132

1

yeah I tried it out a couple months ago on a jsperf - shift and unshift did indeed perform closer to O(n) than O(1), and were a lot slower with large n. made this Queue implementation to avoid shift and unshift https://gist.github.com/tbjgolden/142f2e0b2c1670812959e3588c4fa8a2 – tbjgolden Apr 11 '20 at 19:52
1

@TomGolden - Sorry, not to be too abrupt here, but that implementation needs several caveats. It *never* lets anything go. It accumulates not only unused array slots, but it also holds references to objects in those unused array slots. If you push large objects into that queue, it will hold them *forever*, causing memory usage to go up on O(n) if the size of the total items added during the usage of the queue. At the very least, please set the array slots to undefined after removing them with dequeue. – huntharo Aug 27 '21 at 18:04

score -13 · Answer 4 · answered Jan 16 '17 at 17:18

-13

slice is only linear if the number be taken is unknown. If the slice number is constant, then slice is constant, not linear.

answered Jan 16 '17 at 17:18

Seth Koch

3
1

13

The same can be said of any algorithm. If the number of elements in the array is constant, then you could say sorting the array is a constant time operation. For obvious reasons, this is not very useful information, hence all the downvotes. – Michael Dorst Nov 24 '19 at 04:25

JavaScript runtime complexity of Array functions

4 Answers4

Linked

Related