When comparing algorithms, most people think about speed — but memory is just as important. A blazing-fast algorithm that needs more RAM than your computer has is just as useless as a slow one. Space complexity measures how much extra memory an algorithm uses as its input grows.
What Is Space Complexity?
Space complexity is the total memory an algorithm needs, expressed relative to the input size n. Like time complexity, it is described using Big O notation.
It includes:
- Input space — memory for the input data itself (usually ignored in analysis).
- Auxiliary space — extra memory the algorithm creates during its execution (this is what we focus on).
When people say "space complexity" they usually mean auxiliary space — the additional memory the algorithm needs beyond the input. The input has to exist somewhere regardless, so it is usually not counted.
O(1) — Constant Space
An algorithm uses O(1) (constant) space if it only creates a fixed number of extra variables, regardless of how large the input is.
def find_max(items):
maximum = items[0] # one extra variable
for item in items:
if item > maximum:
maximum = item
return maximum
No matter how long items is — 10 or 10 million — this function only ever creates one extra variable (maximum). Space complexity: O(1).
In-place algorithms (those that sort or process a list without creating new copies) typically have O(1) auxiliary space. Bubble sort and selection sort are O(1) space.
O(n) — Linear Space
An algorithm uses O(n) space if it creates additional data structures whose size grows with the input.
def double_all(items):
result = [] # new list, grows with input
for item in items:
result.append(item * 2)
return result
The result list holds n items, so memory usage grows linearly with n. Space complexity: O(n).
Python's sorted() function creates a new sorted list, so it uses O(n) space. In-place sort methods like list.sort() sort the original list without creating a copy and use O(log n) space (only for the recursive call stack).
O(n²) — Quadratic Space
Some algorithms create 2D structures:
def create_distance_table(points):
n = len(points)
table = [[0] * n for _ in range(n)] # n × n grid
return table
This creates an n × n grid, using n² memory cells. For 1,000 points, that is 1,000,000 entries.
Time vs Space Trade-offs
Improving time complexity sometimes means using more memory, and saving memory sometimes makes an algorithm slower. This is called the time-space trade-off.
| Algorithm | Time complexity | Space complexity |
|---|---|---|
| Bubble sort | O(n²) | O(1) |
| Merge sort | O(n log n) | O(n) |
| Binary search | O(log n) | O(1) |
| Building a lookup table | O(1) search | O(n) to store |
On devices with limited memory (such as embedded systems or microcontrollers), space complexity can be just as important as time complexity — sometimes more so. Always consider both dimensions when choosing an algorithm.
Recursion and the Call Stack
Recursive algorithms use memory for each function call stored on the call stack:
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
factorial(100) creates 100 stack frames. This is O(n) space. Very deep recursion can cause a stack overflow error.
Comparing Space Complexities
From least to most memory:
O(1) < O(log n) < O(n) < O(n log n) < O(n²)
Practice Problems
A function receives a list of n numbers and creates a new list containing only the even numbers. What is its space complexity and why?
Show answer
Selection sort rearranges items in the original list without creating any new lists. What is its space complexity? How does this compare to an algorithm that creates a copy of the list?