Space Complexity: How to Analyze Memory Usage in Algorithms
- Space complexity = auxiliary memory (extra space beyond the input), not total memory.
- O(1) space means the algorithm uses constant extra memory regardless of input size — the gold standard for memory efficiency.
- Recursive algorithms use O(depth) space on the call stack. Deep recursion on large inputs causes StackOverflowError even if the algorithm logic looks correct.
Time complexity gets the headlines in algorithm discussions, but space complexity is what triggers production incidents. I've been called in to diagnose OOM crashes where a developer loaded a 500MB dataset into a HashMap for O(1) lookups without thinking about the 500MB cost. Space complexity analysis prevents that class of mistake before it reaches production.
Space Complexity Analysis with Examples
Auxiliary space is extra memory used by the algorithm excluding the input. Total space = input + auxiliary. Big-O space complexity by convention refers to auxiliary space.
Key insight: recursive algorithms use O(depth) space on the call stack, even if they look like O(1) at a glance.
from typing import List # ── O(1) SPACE ──────────────────────────────────────────────────────────────── def find_max(nums: List[int]) -> int: """Only 'max_val' extra — constant regardless of input size.""" max_val = nums[0] for n in nums: if n > max_val: max_val = n return max_val # Auxiliary space: O(1) # ── O(n) SPACE ──────────────────────────────────────────────────────────────── def reverse_copy(nums: List[int]) -> List[int]: """Returns a new list same size as input.""" return nums[::-1] # Auxiliary space: O(n) — the reversed copy def reverse_in_place(nums: List[int]) -> None: """Swaps in-place — no new list.""" left, right = 0, len(nums) - 1 while left < right: nums[left], nums[right] = nums[right], nums[left] left += 1; right -= 1 # Auxiliary space: O(1) # ── O(n) SPACE — recursive call stack ───────────────────────────────────────── def factorial_recursive(n: int) -> int: """n recursive calls on the stack simultaneously.""" if n <= 1: return 1 return n * factorial_recursive(n - 1) # Auxiliary space: O(n) — call stack depth = n def factorial_iterative(n: int) -> int: """Same result, O(1) space.""" result = 1 for i in range(2, n + 1): result *= i return result # Auxiliary space: O(1) # ── O(log n) SPACE — recursive binary search ────────────────────────────────── def binary_search_recursive(arr, target, lo, hi): if lo > hi: return -1 mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: return binary_search_recursive(arr, target, mid+1, hi) return binary_search_recursive(arr, target, lo, mid-1) # Auxiliary space: O(log n) — recursion depth is log n def binary_search_iterative(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid elif arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1 # Auxiliary space: O(1) # ── O(n²) SPACE — 2D grid ───────────────────────────────────────────────────── def adjacency_matrix(n: int) -> List[List[int]]: """n×n matrix — dangerous at large n.""" return [[0] * n for _ in range(n)] # Auxiliary space: O(n²) — at n=10,000 this is 100M entries = ~400MB print(find_max([3, 1, 4, 1, 5, 9, 2, 6])) # 9 print(factorial_recursive(5), factorial_iterative(5)) # 120 120
120 120
# Space summary:
# find_max: O(1)
# reverse_copy: O(n)
# reverse_in_place: O(1)
# factorial_recursive: O(n) ← call stack
# factorial_iterative: O(1)
# binary_search_recursive: O(log n) ← call stack
# binary_search_iterative: O(1)
# adjacency_matrix(n=10000): O(n²) ≈ 400MB
| Space Complexity | Example Algorithm | Memory at n=1,000,000 |
|---|---|---|
| O(1) | In-place reversal, iterative binary search | Bytes — constant |
| O(log n) | Recursive binary search call stack | ~20 stack frames |
| O(n) | Hash set, array copy, recursive factorial | ~8MB (8 bytes/element) |
| O(n log n) | Merge sort auxiliary array | ~160MB |
| O(n²) | Adjacency matrix, 2D DP table | ~8GB — dangerous |
🎯 Key Takeaways
- Space complexity = auxiliary memory (extra space beyond the input), not total memory.
- O(1) space means the algorithm uses constant extra memory regardless of input size — the gold standard for memory efficiency.
- Recursive algorithms use O(depth) space on the call stack. Deep recursion on large inputs causes StackOverflowError even if the algorithm logic looks correct.
- The iterative version of a recursive algorithm almost always uses less space because it eliminates call stack accumulation.
- O(n²) space — 2D matrices, pairwise lookup tables — becomes dangerous at scale. Audit these before they reach production with large inputs.
⚠ Common Mistakes to Avoid
- ✕Ignoring recursive call stack depth — a recursive DFS on a million-node tree uses O(million) stack space and causes StackOverflowError regardless of how the rest of the algorithm looks.
- ✕Counting input size as auxiliary space — by convention, space complexity in Big-O counts only extra space, not the input itself.
- ✕Using O(n²) space data structures at scale — an adjacency matrix for a graph of 100,000 nodes requires 10 billion entries. Use an adjacency list (O(n + e)) instead.
Interview Questions on This Topic
- QWhat is the space complexity of merge sort?
- QHow does recursive binary search differ from iterative in space complexity?
- QWhat is the space complexity of BFS vs DFS on a graph with n nodes?
- QGive an example where you'd choose higher time complexity to achieve O(1) space.
Frequently Asked Questions
What is space complexity?
Space complexity measures the amount of additional memory an algorithm uses relative to its input size, expressed in Big-O notation. It refers to auxiliary space — extra memory beyond storing the input. O(1) means constant extra memory; O(n) means it grows linearly with input size.
Does recursion use extra space?
Yes. Each recursive call adds a frame to the call stack. A recursion with depth d uses O(d) stack space. For algorithms like merge sort (recursion depth log n) this is O(log n). For linear recursion like factorial(n) it's O(n). This is why very deep recursion on large inputs causes StackOverflowError.
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.