How does creating new arrays affect complexity?
Short answer
Creating a new array most often adds a linear cost: O(n) time due to copying elements and O(n) memory for the new buffer. An empty array can be created in O(1), but as soon as you copy or fill it with data, a linear cost appears. Repeatedly creating new arrays inside loops and recursion can turn an otherwise linear algorithm into a quadratic one because of the repeated copying.
Detailed breakdown
- What "creating a new array" means:
- An empty array or one with a predefined length: creating the shell is usually O(1); filling n elements is O(n).
- A copy of an existing array: O(n) time and O(n) extra memory (copying references/values - usually a shallow copy).
- Operations that return a new array (map, filter, slice, concat, the spread operator): usually O(n) time and O(n) memory; for concatenating two arrays of length n and m - O(n + m).
- Effect on the algorithm's time complexity:
- Copying an array once is an extra linear step (O(n)).
- If copying happens on every loop iteration or every level of recursion, the total complexity can grow to O(n²) because of repeatedly copying ever-longer arrays.
- Effect on space complexity:
- A new array requires O(n) extra memory.
- Compositions like filter().map() create intermediate arrays, increasing peak memory usage.
- Reallocations and amortization:
- Appending to the end of the original array is usually amortized O(1) thanks to spare capacity.
- If instead you create a new array every time (for example, via concat), the amortization benefit is lost: every element gets copied.
- Pre-allocating the length helps avoid repeated resizes.
- GC and cache memory:
- Many temporary arrays increase pressure on the garbage collector.
- Copying large blocks of data hurts locality and can cause CPU-level cache misses.
- Immutability and functional style:
- In an immutable style, new arrays are a normal price for predictability and the absence of side effects.
- Regular arrays in JavaScript do not use structural sharing, so copying costs O(n). Persistent data structures smooth out this cost, but those are a different kind of structure.
Examples and comparisons
Copying and concatenation: time and memory.
const n = 100000;
const a = Array.from({ length: n }, (_, i) => i);
// O(n): a copy
const b = a.slice();
// O(n): a copy
const c = [...a];
// O(n + m): a copy of both arrays
const d = a.concat(c);
// O(n) time, O(n) extra memory due to the intermediate array after filter
const res = a.filter(x => x % 2 === 0).map(x => x * 2);Immutable growth via concat in a loop leads to quadratic complexity.
const n = 100000;
const items = Array.from({ length: n }, (_, i) => i);
// Bad: O(n^2) because the array is copied on every step
let out = [];
for (const x of items) {
out = out.concat([x]); // every concat copies out entirely
}
// Good: O(n) amortized
let out2 = [];
for (const x of items) {
out2.push(x); // amortized O(1) per step
}Removing an element: in-place versus creating a new array.
const a = [1, 2, 3, 4, 5];
const target = 3;
// In-place: O(n) time (shifting), O(1) extra memory
const i = a.indexOf(target);
if (i !== -1) a.splice(i, 1);
// Immutable: O(n) time, O(n) memory (a new array)
const a2 = a.filter(x => x !== target);Copying in recursion: how linear turns into quadratic.
// Bad: a new array is created on every step via concat => O(n^2) total
function recBuild(n, acc = []) {
if (n === 0) return acc;
return recBuild(n - 1, acc.concat(n));
}
// Better: mutate the accumulator (if that is allowed) => O(n)
function recBuildBetter(n, acc = []) {
if (n === 0) return acc;
acc.push(n);
return recBuildBetter(n - 1, acc);
}Pre-allocating and filling without extra copies.
const n = 100000;
const arr = new Array(n); // pre-allocate the length
for (let i = 0; i < n; i++) {
arr[i] = i * 2; // O(n) with no intermediate arrays
}
// An alternative without intermediate copies: one pass instead of filter().map()
const src = Array.from({ length: n }, (_, i) => i);
const doubledEvens = [];
for (let i = 0; i < src.length; i++) {
const x = src[i];
if ((x & 1) === 0) doubledEvens.push(x * 2);
}When creating new arrays is justified
- Immutable state updates in the UI: predictability and simple change detection.
- Pure functions and testability: the absence of side effects matters more than small overhead.
- Snapshots, undo, change history: an independent copy of the data is needed.
- Parallel/asynchronous processing: to rule out races when mutating shared state.
- The volume is small or the operation is rare, and code readability matters more than micro-optimizations.
Practical recommendations
- Do not copy the array on every loop step; use push, accumulators, and pre-allocating the length.
- Avoid arr = arr.concat(x) in hot paths; prefer push, or push with spread operators if it is a single array.
- Merge several passes into one when resources matter: use a single loop or reduce instead of filter().map().
- Profile for large n: check time, peak memory, and garbage collector activity.
- If immutability is required, consider persistent data structures with structural sharing to lower the copying cost.
- Remember: spread and slice are O(n) copies, use them deliberately.
- Frequent insertions/deletions in the middle of an array still cost O(n) time; for such patterns, consider other structures or a different approach.
Summary
Creating new arrays is, as a rule, a linear cost in time and memory. A one-off copy is fine, but regular copying inside loops and recursion quickly accumulates cost and can turn an algorithm quadratic. Choose deliberately between immutability and performance: where speed matters, prefer a single pass, in-place operations, and pre-allocation; where predictability matters, prefer immutable approaches, but without unnecessary copies.
Short Answer
Interview readyPremium
A concise answer to help you respond confidently on this topic during an interview.