Space Complexity
DSA · Introduction to DSA
Theory
Space complexity measures how much extra memory an algorithm needs as the input grows, again written in Big O. It counts auxiliary space such as new arrays, hash tables and the recursion call stack, not usually the input itself. Reversing a list in place uses O(1) extra space, while building a reversed copy uses O(n). Recursive algorithms use stack space proportional to their recursion depth.
Why we use it
Memory is limited, especially on mobile devices, in serverless functions and when processing big data. Many problems have a time-space trade-off: you can often run faster by storing more (for example memoisation or hash tables).
When to use it
Consider space whenever you create copies of data, use recursion, cache results, or work with data that may not fit in memory.
How it works
- Start
- List extra variables, arrays and structures created
- Include recursion stack depth
- Does extra memory grow with n? Yes: Space is O(n) or more. No: Space is O(1).
- Report auxiliary space (exclude the input itself)
Syntax
O(1) a few variables (in-place swap, two pointers)
O(n) a copy of the input, a hash map of n items
O(n²) a 2-D table such as an n x n DP grid
Recursion depth d -> O(d) stack spaceExample
def reverse_copy(arr):
return arr[::-1] # O(n) extra space
def reverse_in_place(arr):
i, j = 0, len(arr) - 1 # O(1) extra space
while i < j:
arr[i], arr[j] = arr[j], arr[i]
i += 1
j -= 1
return arr
data = [1, 2, 3, 4, 5]
print("Copy:", reverse_copy(data), "original kept:", data)
print("In place:", reverse_in_place(data))Key points
- Count the extra memory the algorithm creates
- In-place algorithms use O(1) extra space
- Recursion uses stack space for every active call
- Trading memory for speed is a common, valid design choice