Space complexity describes how much memory an algorithm requires as the size of its input grows — it is the memory equivalent of time complexity. Just as time complexity asks "how many steps?", space complexity asks "how much RAM?", using Big O notation to express the answer in terms of input size n.
What does space complexity measure?
Space complexity counts the extra memory an algorithm allocates beyond the input itself — this is called auxiliary space. (Some definitions include the input; most GCSE-level questions focus on auxiliary space, since the input size is fixed by the problem.)
If you sort a list of n items entirely by swapping elements within the original list (no extra list created), the auxiliary space is a handful of temporary variables — a constant amount regardless of n. That is O(1) space.
If you sort by creating a brand-new list of the same size, the auxiliary space grows proportionally to n. That is O(n) space.
Common space complexities with examples
| Space complexity | Meaning | Example |
|---|---|---|
| O(1) — constant | Fixed extra memory, regardless of n | Bubble sort, insertion sort (in-place) |
| O(log n) — logarithmic | Extra memory grows slowly (typically a recursion stack) | Binary search (recursive), quicksort recursion stack |
| O(n) — linear | Extra memory proportional to input size | Merge sort (temporary arrays), storing a copy of input |
| O(n²) — quadratic | Extra memory proportional to n² | Storing a full n×n adjacency matrix for a graph |
O(1) space: in-place algorithms
An in-place algorithm modifies the input directly and uses only a small, constant number of extra variables — O(1) auxiliary space.
Bubble sort worked example (space):
def bubble_sort(lst):
n = len(lst) # 1 integer variable
for i in range(n - 1): # loop counter i: 1 integer
for j in range(n - 1 - i): # loop counter j: 1 integer
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j] # swap: no extra list
return lst
Extra variables used: n, i, j — three integers regardless of how large the input list is. Space complexity: O(1).
O(n) space: merge sort and the cost of extra memory
Merge sort is the classic example of an algorithm that is faster (O(n log n) time vs O(n²) for bubble sort) but uses more memory.
To merge two sorted halves, merge sort must create a temporary array to hold the merged result — it cannot merge in-place efficiently. For an input of n items, the temporary arrays at any one moment require O(n) extra space.
Input: [5, 3, 8, 1, 4, 2, 9, 6] — n = 8
Splits: [5, 3, 8, 1] [4, 2, 9, 6]
[5, 3] [8, 1] [4, 2] [9, 6]
...
Merge: needs a temp array of size 2, then 4, then 8 — O(n) total
Space complexity of merge sort: O(n).
The time–space trade-off
Every algorithm makes an implicit bargain between time and memory. You can often spend more memory to save time, or save memory at the cost of extra computation:
| Trade-off direction | Example | Time | Space |
|---|---|---|---|
| Speed over memory | Memoisation (store computed results) | O(n) | O(n) |
| Memory over speed | Recompute instead of storing | O(n²) | O(1) |
| Speed over memory | Merge sort | O(n log n) | O(n) |
| Memory over speed | Bubble sort (in-place) | O(n²) | O(1) |
Memoisation example: Computing the nth Fibonacci number naïvely (without memoisation) recalculates the same sub-values exponentially many times — O(2ⁿ) time, O(n) stack space. With memoisation (storing results in a dictionary), it runs in O(n) time but requires O(n) extra space for the dictionary. Massive time saving; modest space cost.
Why does space complexity matter in practice?
- Embedded systems (microcontrollers in washing machines, traffic lights) may have only kilobytes of RAM. An O(n) space algorithm that needs a megabyte would simply fail.
- Mobile apps must be mindful of RAM because the operating system can terminate an app that uses too much memory.
- Large-scale data processing (sorting gigabytes of log files) may not be able to hold a full copy of the data in RAM — an in-place algorithm with O(1) auxiliary space is essential.
- In competitive programming and GCSE exam questions, space constraints may be stated explicitly: "your algorithm must use O(1) extra space".
Frequently asked questions
Is space complexity the same as memory usage?
Space complexity is a measure of how memory usage scales with input size — expressed as Big O — not the actual number of bytes. An algorithm with O(1) space still uses some memory (for the program itself, the input, and a few variables), but the amount does not grow as the input grows. Actual memory usage depends on data type sizes, programming language, and compiler.
Does recursion always use more memory?
Recursive algorithms typically use O(depth) stack space because each recursive call adds a stack frame to the call stack. For binary search, the recursion depth is O(log n), so stack space is O(log n). For a naive recursive Fibonacci, the depth can be O(n). An iterative equivalent of the same algorithm usually uses O(1) stack space, which is why deep recursion can cause a stack overflow even when the total work is manageable.
Which has better space complexity — bubble sort or merge sort?
Bubble sort uses O(1) auxiliary space (in-place). Merge sort uses O(n) auxiliary space (needs temporary arrays for merging). So bubble sort wins on space. However, merge sort wins on time (O(n log n) vs O(n²)). This is a classic time–space trade-off: merge sort is a better choice when time matters more than memory; bubble sort is preferable on severely memory-constrained devices with small inputs.
Can you achieve both O(n log n) time and O(1) space for sorting?
Heapsort achieves O(n log n) time and O(1) auxiliary space — it is the only commonly known comparison sort with both properties. However, it is not stable (it can change the relative order of equal elements) and tends to have worse cache performance than merge sort in practice, so it is less commonly used despite its theoretical appeal.
Professor Turing at aitutors.me will set you space-complexity challenges and guide your reasoning — no answers given outright, always the next insight.