What is Space Complexity?
Space complexity describes how much memory an algorithm uses as the input size grows.
Just like time complexity uses Big O to describe running time, space complexity uses Big O to describe memory usage. The same rules apply: ignore constants, keep the dominant term.
Space complexity matters because memory is finite. An algorithm that uses O(n²) memory on a million-element input will run out of RAM long before it finishes.
Two Types of Memory to Count
When calculating space complexity, you count two things:
Input space — the memory used by the input itself. Since the input is given to you, some analyses exclude this and only count auxiliary space.
Auxiliary space — the extra memory your algorithm uses beyond the input. Variables, data structures you create, recursive call frames on the stack.
Most interviews and textbooks mean auxiliary space when they say "space complexity." But you'll see both conventions — just clarify which one is being discussed.
Common Space Complexities
O(1) — Constant Space
The algorithm uses the same amount of memory regardless of input size. Only a fixed number of variables.
Linear search, bubble sort (in-place), and most two-pointer techniques are O(1) auxiliary space.
O(n) — Linear Space
Memory usage grows proportionally with the input.
Also: building a hash map of all elements is O(n) space.
O(log n) — Logarithmic Space (Recursion)
Binary search done recursively uses O(log n) stack space — one frame per level of recursion, and there are log n levels.
The iterative version of binary search uses O(1) space — no recursion, no stack frames.
O(n) Space from Recursion
Deep recursion (like naive Fibonacci or DFS on a long chain) can use O(n) stack space — one frame per call, and calls go n levels deep.
O(n²) — Quadratic Space
Creating an n×n grid or matrix.
Time vs Space Trade-offs
Very often, you can trade memory for speed (or vice versa). This is one of the most important concepts in algorithm design.
Example: Counting duplicates
Approach 1 — O(1) space, O(n²) time:
Approach 2 — O(n) space, O(n) time:
Approach 2 uses more memory but runs in linear time instead of quadratic. The hash set is the trade — you pay memory to save time.
This trade-off appears everywhere:
- Memoization: cache results (more memory) to avoid re-computation (less time)
- Lookup tables: pre-compute answers (more memory) for O(1) queries (less time)
- In-place sorting: sort without a second array (less memory) but sometimes slower or more complex
Recursive Algorithms and the Call Stack
Recursion's space cost is invisible until it causes a stack overflow. Every function call adds a frame to the call stack. Each frame stores:
- The local variables of that call
- The return address
- The parameters
For a recursion that goes n levels deep, that's n frames on the stack. Default stack sizes are typically 1–8 MB, which limits recursion depth to roughly 10,000–100,000 levels depending on frame size.
Tail recursion eliminates this: if a function's last action is the recursive call (no work to do after it returns), some languages/compilers convert it to a loop automatically, saving the stack space.
How to Analyse Space Complexity
- Count variables — each scalar variable is O(1).
- Count data structures you allocate — an array of n elements is O(n), an n×n matrix is O(n²).
- Count recursion depth — each stack frame costs memory proportional to the frame's local variables (usually O(1) per frame).
- Take the maximum — if one part of the algorithm uses O(n) and another uses O(n²), the total is O(n²).
- Input space usually doesn't count — unless the problem says otherwise, only count auxiliary space.
Quick Reference
| Algorithm | Time | Space |
|---|---|---|
| Linear search | O(n) | O(1) |
| Binary search (iterative) | O(log n) | O(1) |
| Binary search (recursive) | O(log n) | O(log n) |
| Bubble sort | O(n²) | O(1) |
| Merge sort | O(n log n) | O(n) |
| Quick sort | O(n log n) avg | O(log n) avg |
| Hash map lookup | O(1) avg | O(n) |
| DFS (graph) | O(V + E) | O(V) |
| BFS (graph) | O(V + E) | O(V) |
| Naive Fibonacci | O(2^n) | O(n) |
| Fibonacci (memoized) | O(n) | O(n) |