What is the runtime complexity of JavaScript array spread syntax?

Question

Let's say I want to copy an existing array using the array spread syntax, like this:

const a = [1, 2, 3, ..., n];
const b = [...a]

What would be the runtime complexity of const b = [...a]? I can't seem to find any info about that.

Side note: ... is not an operator. Operators can't do what ... does. ... is primary syntax. — T.J. Crowder
– T.J. Crowder, Commented Feb 20, 2021 at 13:38
Do you know what the syntax does? Do you know what the runtime complexity of "copying an array" is? — Bergi
– Bergi, Commented Feb 20, 2021 at 14:03
@Bergi According to mdn, the spread syntax "allows an iterable such as an array expression or string to be expanded in places where zero or more arguments (for function calls) or elements (for array literals) are expected", ie it expands the array in our case. So it seems like it should be O(n). But I'm not really sure what happens under the hood - maybe js is doing some kind of optimizations if called like const b = [...a]? — Maksym
– Maksym, Commented Feb 20, 2021 at 19:25
@Maksym Yes, exactly that. Under the hood it runs the iterator, although of course for arrays the engine might optimise this to not create an iterator object and repeatedly call next() on it (and also can allocate the new array with the right size). It still has to copy all elements from one array to the new one, just like .slice() would, which is O(n). — Bergi
– Bergi, Commented Feb 20, 2021 at 20:15

T.J. Crowder · Accepted Answer · 2021-02-20 14:15:15Z

5

Theoretically, it's a bit of up-front cost and then linear (assuming a standard array iterator, not something custom), since theoretically it's a loop consuming the iterator from the array, like this:

const a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const b = [];
for (const element of a) {
    b[b.length] = element;
}
console.log(b);

which, in turn, is effectively:

const a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const b = [];
{
    const it = a[Symbol.iterator]();
    let result;
    while (!(result = it.next()).done) {
        const element = result.value;
        b[b.length] = element;
    }
}
console.log(b);

(In that specific [...a] case, even with minimal optimizaton the JavaScript engine may be able to get rid of the iterator overhead and make it simply linear, like a.slice() would.)

Even if optimized by the JavaScript engine (e.g., if it's in a hotspot in the code), it's not clear how it could do better than linear, since even a memcopy operation is linear.

I said "assuming the standard array iterator" because not all iterators are necessarily linear. The standard array iterator is linear, but that doesn't mean all iterators are.

edited Feb 20, 2021 at 14:15

answered Feb 20, 2021 at 13:38

T.J. Crowder

1.1m201 gold badges2k silver badges2k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

T.J. Crowder Over a year ago

FWIW, I go into ... (rest and spread) syntax, iterators, iterables, etc. in Chapters 3, 5, and 6 (and probably touch on them elsewhere) of my recent book JavaScript: The New Toys. Links in my profile if you're interested.

Bergi Over a year ago

…and of course, if you happen to have an iterator that does increasing work per step (say, computing primes), it'll be above linear. OP asked specifically about copying arrays though, and for these it's definitely linear.

Collectives™ on Stack Overflow

What is the runtime complexity of JavaScript array spread syntax?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related