Time and Space Complexity Trade-offs in JavaScript

The problem

What's the time and space complexity of your solution — and what would it cost to make it faster?

The complexity question is rarely about reciting "O(n log n)." It's about reasoning: can you name the cost of your approach, spot the accidental quadratic, and articulate the trade you're making when you speed it up? Almost every optimization is the same deal — spend memory to buy time — and the senior signal is knowing when that deal is worth taking.

The one-liner: complexity isn't the answer; the trade-off you choose is.

Big-O, fast

Big-O describes growth, not wall-clock time. O(n²) can beat O(n) for small n — constants and memory pressure matter — which is exactly why you measure instead of assuming.

The core trade: memory for speed

The canonical example is finding pairs. Nested scan — O(n²) time, O(1) space:

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
}

Trade O(n) memory for O(n) time by remembering what you've seen:

function twoSum(nums, target) {
  const seen = new Map(); // value → index  (this Map IS the space you're spending)
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
}

Same shape as memoization and the LRU cache: a lookup table converts repeated work into an O(1) read. The interviewer's follow-up — "what did that cost?" — wants you to say "O(n) extra memory," not stay silent.

The JavaScript data-structure cheat sheet

Choosing the right structure often is the optimization:

Practical rules that come up constantly:

• Membership test in a loop? Convert the array to a Set first. arr.filter(x => big.includes(x)) is O(n·m); const s = new Set(big); arr.filter(x => s.has(x)) is O(n).
• Map over object when keys aren't strings, when you need .size or ordered iteration, or when keys are user-controlled (objects have prototype-pollution footguns like a "__proto__" key).
• arr.shift() / unshift() are O(n) — they reindex every element. A queue built on shift() is a hidden quadratic; use two pointers or a real deque for hot paths.

The accidental quadratic

The most common real bug isn't a nested loop you can see — it's an O(n) operation inside an O(n) loop:

// ❌ O(n²): each spread copies the whole growing array
let result = [];
for (const x of items) result = [...result, transform(x)];
 
// ✅ O(n): push mutates in place, amortized O(1)
const result = [];
for (const x of items) result.push(transform(x));

Watch for these hidden linear costs firing per-iteration: spread ([...arr], {...obj}) copies, array.includes/indexOf, string += concatenation in a loop, JSON.parse/stringify, and re-running arr.length-dependent work you could hoist out.

function dedupe(arr) {
return arr.filter((x, i) => arr.indexOf(x) === i);
}

Amortized analysis: why push is "O(1)"

A dynamic array occasionally has to grow its backing store and copy everything — an O(n) event. But it grows geometrically (doubling), so those copies are rare enough that the cost averaged over all pushes is constant. That's amortized O(1). The same reasoning explains why hash-based Map/Set operations are "O(1)" despite occasional rehashing. Interviewers love this because it separates people who memorized a table from people who understand it.

Space you forget to count

• The call stack. Recursion is O(depth) space — a recursive tree walk is O(h), and unbounded recursion blows the stack. An iterative version with an explicit stack trades stack frames for heap.
• Memoization tables (memoize, DP arrays) are literal space-for-time and grow unbounded without eviction — see garbage collection & leaks.
• In-place vs copy. arr.sort() mutates (O(1) extra); [...arr].sort() is O(n) space but keeps the input pristine. Which one you want is a real design choice, not a detail.

When O(n²) is the right answer

The senior move is not always reaching for the clever structure:

• Small, bounded n — a nested loop over 10 items is invisible and reads more clearly than a Map you have to explain.
• Clarity under interview time — get the O(n²) version working and correct, then say "I can take this to O(n) with a hash map, trading O(n) memory — want me to?" That sequencing scores higher than a buggy clever attempt.
• Memory-constrained contexts where the O(1)-space version is the requirement.

"It depends on n and whether memory or readability is tighter" is a better answer than blindly optimizing.

Interview follow-ups to be ready for

• "Can you do better?" Usually means "trade memory for time with a hash structure." Say the cost of the trade out loud.
• "What's the space complexity?" Count auxiliary structures and the call stack. The input itself usually doesn't count unless you copy it.
• "Why is Object.keys(obj).length not O(1)?" It builds an array of every key — O(n). map.size is the O(1) equivalent, one more reason to reach for Map.
• "Best, average, or worst case?" Hash lookups are O(1) average but O(n) worst case under collisions; sort is O(n log n). Naming the case shows you know Big-O is a family, not a single number.