DSA · Chapter 3 of 40
Space Complexity
Space complexity measures the extra memory an algorithm needs beyond the input. An in-place algorithm uses O(1) extra space; one that builds a copy of the data uses O(n).
Interviewers often ask for a solution that is fast and uses little extra memory, so it helps to know which approach allocates and which does not.
Auxiliary space
Only the extra memory counts. Reversing a list in place is O(1) auxiliary space even though the list itself is O(n).
Recursion costs memory
Every recursive call adds a frame to the call stack, so a recursion of depth n costs O(n) space even if it allocates nothing.
Example 1 (python)
# O(1) extra space: reverse in place
nums = [1, 2, 3, 4]
i, j = 0, len(nums) - 1
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
print(nums)Output
[4, 3, 2, 1]Swapping uses only two index variables.
Example 2 (python)
# O(n) extra space: build a new list
nums = [1, 2, 3, 4]
rev = nums[::-1]
print(rev)Output
[4, 3, 2, 1]Slicing creates a full copy, so memory grows with n.
Key points
- Space complexity counts extra (auxiliary) memory.
- In-place algorithms use O(1) extra space.
- Recursion depth n costs O(n) stack space.
- Hash maps trade memory for speed.
💡 Note: Time and space are a trade-off — say which one you are optimising and why.