Search code examples
javascripttime-complexityslicev8

Time complexity of slice in javascript v8 runtime


As per MDN

The slice() method returns a shallow copy of a portion of an array

That means you could effectively just return the pointer to the starting index in O(1) time complexity. But in many discussions, I see O(n) specified (linked below).

Links:

Was taking a look into v8 implementation but didn't get it.
https://chromium.googlesource.com/v8/v8/+/4.3.49/src/string.js?autodive=0%2F%2F


Solution

  • (V8 developer here.)

    Array.prototype.slice is O(n), where n is the number of elements in the slice.
    String.prototype.slice is O(1), thanks to our implementation of SlicedStrings, which are just storing pointer, offset, length to the original string and avoid copying the characters (except when they're tiny, so that copying a handful of characters is actually cheaper and smaller than storing a reference; that's still O(1)).

    The key difference is that strings are immutable, and arrays are not. When you do str1 = "Hello World"; str2 = str1.slice(2, 5);, since there is no way to modify str1's contents afterwards, str2 doesn't need to ensure that it's unaffected by any such modification.
    When you do a = [1, 2, 3, 4]; b = a.slice(1, 3); a[1] = "changed"; console.log(b[0]);, then you expect to see 2, not "changed". That's why b has to be an actual copy. (In theory, a copy-on-write approach would be possible, but V8 doesn't do that for array slices.)

    "Shallow copy" means that nested objects will not be copied. Example:

    let nested = {property: "value"};
    var a = [nested];
    var b = a.slice(0, 1);
    a[0].property = "new value";
    console.log(a === b);          // false, `b` is a copy
    console.log(a[0] === b[0]);    // true, `nested` was not copied
    console.log(b[0] === nested);  // true
    console.log(b[0].property);    // "new value"