What’s the time complexity of array.splice() in Google Chrome?

by

Worst case should be O(n) (copying all n-1 elements to new array).

A linked list would be O(1) for a single deletion.

For those interested I’ve made this lazily-crafted benchmark. (Please don’t run on Windows XP/Vista). As you can see from this though, it looks fairly constant (i.e. O(1)), so who knows what they’re doing behind the scenes to make this crazy-fast. Note that regardless, the actual splice is VERY fast.

Rerunning an extended benchmark directly in the V8 shell that suggest O(n). Note though that you need huge array sizes to get a runtime that’s likely to affect your code. This should be expected as if you look at the V8 code it uses memmove to create the new array.

More Related Contents:

  1. Object descriptor getter/setter performance in recent Chrome/V8 versions
  2. Big O of JavaScript arrays
  3. Using ‘let’ as a variable name is not throwing any errors in google v8
  4. Accessing line number in V8 JavaScript (Chrome & Node.js)
  5. Chrome extension that enables chatting with users on same page [closed]
  6. Is Chrome’s JavaScript console lazy about evaluating objects?
  7. Find out whether Chrome console is open
  8. How to import ES6 modules in content script for Chrome Extension
  9. Video auto play is not working in Safari and Chrome desktop browser
  10. Unchecked runtime.lastError while running tabs.executeScript?
  11. TypeError: Illegal Invocation on console.log.apply
  12. How to detect when a tab is focused or not in Chrome with Javascript?
  13. How do I auto-reload a Chrome extension I’m developing?
  14. Editing in the Chrome debugger
  15. Executing JavaScript without a browser?
  16. Upload File as a Form Data through chrome extension
  17. Getting Chrome to prompt to save password when using AJAX to login
  18. Refused to execute inline event handler because it violates CSP. (SANDBOX)
  19. How can I make window.showmodaldialog work in chrome 37?
  20. Chrome javascript debugger breakpoints don’t do anything?
  21. Is it possible for XHR HEAD requests to not follow redirects (301 302)
  22. How can I save information locally in my chrome extension?
  23. How to get the currently opened tab’s URL in my page action popup?
  24. How to find JS Memory Leaks?
  25. Is it possible to remove “Inspect Element”?
  26. Why are function declarations handled differently in different browsers?
  27. Javascript / Chrome – How to copy an object from the webkit inspector as code
  28. Jenkins error – Blocked script execution in . because the document’s frame is sandboxed and the ‘allow-scripts’ permission is not set
  29. blocked a frame of origin “null” from accessing a cross-origin frame – chrome
  30. How is Google Meet able to show CPU usage?

Leave a Comment