JavaScript runtime complexity of Array functions

by

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.

More Related Contents:

  1. How do I check if an array includes a value in JavaScript?
  2. Big O of JavaScript arrays
  3. How to insert an item into an array at a specific index (JavaScript)
  4. Deleting array elements in JavaScript – delete vs splice
  5. Does JavaScript have a method like “range()” to generate a range within the supplied bounds?
  6. Remove Object from Array using JavaScript
  7. Remove all elements contained in another array
  8. In javascript, how do you search an array for a substring match
  9. Get the index of the object inside an array, matching a condition
  10. How to get first N number of elements from an array
  11. Sorting arrays numerically by object property value
  12. What is the most efficient way to concatenate N arrays?
  13. How to know if two arrays have the same values
  14. JavaScript – Difference between Array and Array-like object
  15. Access non-numeric Object properties by index?
  16. Create a and fill it based on a passed array
  17. How are JavaScript arrays represented in physical memory?
  18. Why is the loop assigning a reference of the last index element to? [duplicate]
  19. Convert html table to array in javascript
  20. Group by, and sum, and generate an object for each array in JavaScript
  21. Convert javascript array to string
  22. JavaScript array to CSV
  23. JavaScript – Nuances of myArray.forEach vs for loop
  24. Loop (for each) over an array in JavaScript
  25. In an array of objects, fastest way to find the index of an object whose attributes match a search
  26. How to push object to array from for loop properly in JavaScript?
  27. Can I use document.getElementById() with multiple ids?
  28. Construct hierarchy tree from flat list with parent field? [duplicate]
  29. Filter null from an array in JavaScript
  30. How does one sort a multi dimensional array by multiple columns in JavaScript?

Leave a Comment