Know the Big-O of Every Array Method Before You Reach for It
Array Method Complexity
Every common JavaScript Array method has a concrete time and space complexity — knowing them prevents accidentally writing O(n²) code that looks like O(n).
What you'll learn
- Recall the Big-O time complexity for all common Array methods
- Identify which methods are O(1) vs. O(n) at a glance
- Avoid inadvertently introducing quadratic behaviour in array-heavy code
Every time you call an array method you are making a performance choice. V8 optimises aggressively, but the fundamental algorithmic complexity is fixed by what each operation must do — no optimiser can turn O(n) work into O(1) when all n elements must be examined.
The Complexity Table
| Method | Time | Space | Why |
|---|---|---|---|
| push(x) | O(1) amortised | O(1) | Append to end; occasional resize is amortised |
| pop() | O(1) | O(1) | Remove last element — no shifting |
| shift() | O(n) | O(1) | Every element must be moved down by one index |
| unshift(x) | O(n) | O(1) | Every element must be moved up by one index |
| splice(i, d, …items) | O(n) | O(d) | May shift up to n − i elements |
| slice(i, j) | O(j − i) | O(j − i) | Copies a contiguous range |
| concat(…arrs) | O(n + m) | O(n + m) | Copies both arrays into a new one |
| indexOf(x) | O(n) | O(1) | Linear scan; no hash or binary search |
| includes(x) | O(n) | O(1) | Same linear scan as indexOf |
| find / findIndex | O(n) | O(1) | Stops at first match but worst-case full scan |
| sort() | O(n log n) | O(log n) | TimSort (merge + insertion) in V8 |
| reverse() | O(n) | O(1) | In-place swap of n/2 pairs |
| map(fn) | O(n) | O(n) | New array of same length |
| filter(fn) | O(n) | O(n) worst | New array of up to n elements |
| reduce(fn) | O(n) | O(1) | Single pass, accumulator is reused |
| forEach(fn) | O(n) | O(1) | Same as reduce without return value |
| flat(depth) | O(n * depth) | O(n) | Recursively visits sub-arrays |
| Array.from(iter) | O(n) | O(n) | Materialises the whole iterable |
The Two Traps
Trap 1 — shift inside a loop. Removing from the front is O(n), so a loop
that calls shift n times is O(n²).
// O(n²) — each shift moves remaining elements
function processQueue(items) {
while (items.length) {
handle(items.shift()); // bad for large arrays
}
}
// O(n) — iterate with an index instead
function processQueue(items) {
for (let i = 0; i < items.length; i++) {
handle(items[i]);
}
}Trap 2 — indexOf inside a loop. Searching a large array for each element of another array is O(n * m). Convert the search target to a Set first.
// O(n * m) — indexOf is a linear scan each time
function overlap(a, b) {
return a.filter(x => b.indexOf(x) !== -1);
}
// O(n + m) — Set lookup is O(1)
function overlap(a, b) {
const set = new Set(b);
return a.filter(x => set.has(x));
}Up Next
Now that you know the cost of each array operation, learn the two-pointer pattern — a technique that replaces many O(n²) nested loops with O(n) passes.
Two-Pointer Pattern →