JavaScript runtime complexity of Array functions -

is runtime complexity defined js standard on common array functions push, pop, shift, slice or splice? esp. i'm interested in removing , inserting entries @ random positions. if complexity not defined, can expect, e.g. in v8?

(this question inspired this. also, this benchmark, posted here, makes me curious, maybe unrelated phenomena.)

(a related question here. however, 1 of comments on accepted answer says wrong now. also, accepted answer not have reference standard defines way.).

the ecma specification not specify bounding complexity, however, can derive 1 specification's algorithms.

push o(1), however, in practice encounter o(n) copy costs @ engine defined boundaries slot array needs reallocated. these boundaries typically logarithmic.

pop o(1) similar caveat push o(n) copy encountered folded garbage collection (e.g. copying collector copy used part of array).

shift @ worst o(n) can, in specially cases, implemented o(1) @ cost of slowing down indexing mileage may vary.

slice o(n) n end - start. not tremendous amount of optimization opportunity here without slowing down writes both arrays.

splice is, worst case, o(n). there array storage techniques divide n constant slow down indexing. if engine uses such techniques might notice unusually slow operations switches between storage techniques triggered access pattern changes.

one didn't mention, sort. is, in average case, o(n log n). however, depending on algorithm chosen engine, o(n^2) in cases. example, if engine uses quicksort (even late out insertionsort), has well-known n^2 cases. source of dos application. if concern either limit size of arrays sort (maybe merging sub-arrays) or bail-out heapsort.