What does space complexity mean?

AlgorithmsJunior~3 min read

Short answer

Space complexity is an estimate of how the amount of memory used by an algorithm grows as the size of the input data n increases, usually expressed in O(·) notation. A distinction is often made between total memory (including input and output) and auxiliary memory (only what is extra beyond the input/output).

Detailed breakdown

What space complexity is

Space complexity is a function that describes an upper estimate of the memory an algorithm uses depending on the input size n. It is expressed as O(1), O(log n), O(n), O(n log n), O(n²), and so on.

Auxiliary space: variables, temporary data structures, the recursion stack - everything beyond the input itself and the required output. This is what is usually asked about in interviews.
Total space: input + output + auxiliary space. Clarify what exactly needs to be estimated.

What is taken into account when estimating

The number and size of additional data structures: arrays, lists, hash tables, trees, and so on.
The depth of the call stack under recursion (each stack frame stores local variables and a return address).
The size of the output data (if total memory is being counted). For example, generating all subsets requires O(2^n) space for the result.

Why this matters

Memory constraints: mobile devices, serverless functions, containers with limits.
Scaling: algorithms that require O(n) or O(n²) extra memory may be unacceptable on large data.
Recursion: can quietly "eat" memory through the call stack.

How to estimate it in practice (step by step)

Denote the input size: n (or n and m for two-dimensional cases).
Count the additional structures: arrays/collections and their sizes relative to n.
Account for recursion: stack depth × frame size gives O(depth).
Sum up and keep the dominant term (O(n) + O(1) → O(n)).
Clarify: does the answer need auxiliary or total memory.

Typical examples and their O-complexity

Algorithm/structure	Auxiliary memory	Note
A linear pass with a constant number of variables	O(1)	No extra structures, just counters/pointers
Copying/filtering an array into a new array	O(n)	The new array is proportional to the input size
Merge sort	O(n)	Buffers are needed for merging
Quicksort, recursive, in-place	O(log n) on average	Due to the recursion stack; O(n) in the worst case
DFS/BFS over a graph with a visited set	O(V + E)	Storing the queue/stack and the "visited" set
Binary search (recursive)	O(log n)	The recursion depth is logarithmic; iteratively - O(1)

Code examples (JavaScript)

Reversing an array: O(1) vs O(n) memory

// O(1) auxiliary memory: swap elements in place
function reverseInPlace(arr) {
  let i = 0, j = arr.length - 1;
  while (i < j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
    i++; j--;
  }
  return arr;
}

// O(n) auxiliary memory: build a new array
function reverseWithCopy(arr) {
  const res = [];
  for (let i = arr.length - 1; i >= 0; i--) res.push(arr[i]);
  return res;
}

Recursion and the stack: O(n) versus O(1) iteratively

// Recursive sum: O(n) on the stack
function sumRec(arr, i = 0) {
  if (i === arr.length) return 0;
  return arr[i] + sumRec(arr, i + 1);
}

// Iterative sum: O(1) extra memory
function sumIter(arr) {
  let s = 0;
  for (let x of arr) s += x;
  return s;
}

Checking for duplicates with a Set: O(n) memory

function hasDuplicate(arr) {
  const seen = new Set(); // up to n elements → O(n)
  for (const x of arr) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

Working through an example: Two Sum - trading "memory ↔ time"

The set-based approach: O(n) time and O(n) memory (a Set for numbers already seen).
The sorting plus two-pointers approach: after sorting - O(1) extra memory and O(n) time; but sorting costs O(n log n) time and may require O(log n)-O(n) memory depending on the implementation.

// O(n) memory: Set
function twoSumSet(arr, target) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(target - x)) return true;
    seen.add(x);
  }
  return false;
}

// O(1) extra memory after sorting (if the sort is in-place)
function twoSumTwoPointers(arr, target) {
  arr.sort((a, b) => a - b); // in reality this may require extra memory
  let i = 0, j = arr.length - 1;
  while (i < j) {
    const s = arr[i] + arr[j];
    if (s === target) return true;
    s < target ? i++ : j--;
  }
  return false;
}

Practical tips for interviews

Always clarify: are we estimating auxiliary or total memory.
Talk about the recursion stack: "The solution is recursive, so it is O(depth) in memory".
Point out trade-offs: "I use a Set - O(n) memory, but O(n) time. Without a Set - O(1) memory, but worse time".
Constant memory is not "0 memory" - it is memory that does not depend on n (for example, a few variables or a fixed buffer).

Summary

Space complexity describes how much extra memory an algorithm requires as the input grows. For a confident interview answer: clearly define n, list the extra structures and the recursion stack, pick the dominant order, and explain the trade-offs between time and memory.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.