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.
|
Show 4 more comments
1 Answer
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.
2 Comments
T.J. Crowder
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
…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.