Suggest an edit

Improve this article

Refine the answer for “What does space complexity mean?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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)

1. Denote the input size: n (or n and m for two-dimensional cases).
2. Count the additional structures: arrays/collections and their sizes relative to n.
3. Account for recursion: stack depth × frame size gives O(depth).
4. Sum up and keep the dominant term (O(n) + O(1) → O(n)).
5. 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)

1) 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;
}
```

2) 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;
}
```

3) 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.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts913 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.