Big O of JavaScript arrays

by

NOTE: While this answer was correct in 2012, engines use very different internal representations for both objects and arrays today. This answer may or may not be true.

In contrast to most languages, which implement arrays with, well, arrays, in Javascript Arrays are objects, and values are stored in a hashtable, just like regular object values. As such:

  • Access – O(1)
  • Appending – Amortized O(1) (sometimes resizing the hashtable is required; usually only insertion is required)
  • Prepending – O(n) via unshift, since it requires reassigning all the indexes
  • Insertion – Amortized O(1) if the value does not exist. O(n) if you want to shift existing values (Eg, using splice).
  • Deletion – Amortized O(1) to remove a value, O(n) if you want to reassign indices via splice.
  • Swapping – O(1)

In general, setting or unsetting any key in a dict is amortized O(1), and the same goes for arrays, regardless of what the index is. Any operation that requires renumbering existing values is O(n) simply because you have to update all the affected values.

More Related Contents:

  1. How do I check if an array includes a value in JavaScript?
  2. Cartesian product of multiple arrays in JavaScript
  3. Javascript Array.sort implementation?
  4. How might I find the largest number contained in a JavaScript array?
  5. JavaScript runtime complexity of Array functions
  6. How do I sort an array of objects based on the ordering of another array?
  7. Javascript – Generating all combinations of elements in a single array (in pairs)
  8. Javascript algorithm to find elements in array that are not in another array
  9. What’s the time complexity of array.splice() in Google Chrome?
  10. Sieve of Eratosthenes algorithm in JavaScript running endless for large number
  11. Remove duplicate objects from an array using javascript
  12. Maximum single-sell profit
  13. Get the item that appears the most times in an array
  14. Combine json arrays by key, javascript
  15. Finding all permutations of array elements as concatenated strings
  16. Creating an array consisting of the largest values of each sub-array does not work as expected
  17. Randomizing elements in an array?
  18. How do I empty an array in JavaScript?
  19. How can I add new array elements at the beginning of an array in JavaScript?
  20. Remove array element based on object property
  21. How to get character array from a string?
  22. How to find index of all occurrences of element in array?
  23. Sorting an array of objects by property values
  24. Access non-numeric Object properties by index?
  25. How are JavaScript arrays represented in physical memory?
  26. JavaScript – Nuances of myArray.forEach vs for loop
  27. How to create an array of objects from multiple arrays
  28. How to convert array of key–value objects to array of objects with a single property?
  29. Find closest date in array with JavaScript
  30. Sum values of objects in array

Leave a Comment