AlgorithmsSpace Complexity Guide
💾 Space Complexity Guide
Understand memory usage patterns of algorithms. Learn how to analyze and optimize space complexity.
O(1) - Constant Space
Fixed memory usage regardless of input size
- Variables, primitive types
- Iterative algorithms (binary search, linear search)
- In-place array operations
- Two-pointer techniques
O(log n) - Logarithmic Space
Memory grows logarithmically with input
- Recursive binary search (call stack depth)
- Quick sort recursion (average case)
- Divide and conquer algorithms
- Balanced tree recursion
O(n) - Linear Space
Memory grows proportionally to input
- Arrays, lists, hash tables
- Merge sort auxiliary array
- DFS/BFS visited arrays
- Dynamic programming 1D tables
O(n²) - Quadratic Space
Memory grows quadratically
- 2D DP tables (LCS, Edit Distance)
- Adjacency matrix for graphs
- Distance matrices
- Dynamic programming 2D tables
Space Complexity of Common Algorithms
| Algorithm | Space | Why? |
|---|---|---|
| Iterative Binary Search | O(1) | Only uses a few pointer variables regardless of array size |
| Recursive Binary Search | O(log n) | Call stack depth equals log n recursive calls |
| Merge Sort | O(n) | Needs auxiliary array of size n for merging |
| Quick Sort | O(log n) | Recursion depth is log n in average case |
| Heap Sort | O(1) | Sorts in-place; only uses a few variables |
| Bubble Sort | O(1) | In-place swapping; no extra memory |
| Linear Search | O(1) | Only uses loop counter variable |
| BFS (Graph) | O(V) | Queue may hold up to V vertices; visited array of size V |
| DFS (Graph) | O(V) | Recursion/stack depth up to V; visited array of size V |
| Dijkstra | O(V) | Distance array of size V; priority queue may hold V elements |
| Fibonacci (Tabulation) | O(1) | Only need last two values, not full array |
| LCS (Space Optimized) | O(min(n,m)) | 1D rolling array instead of 2D |
| Adjacency List | O(V+E) | List per vertex; total size is vertices + edges |
| Adjacency Matrix | O(V²) | V×V matrix regardless of edge count |
🚀 Space Optimization Techniques
1
In-Place Algorithms
Modify input directly instead of creating copies. Examples: heap sort, two-pointer techniques, array reversal.
2
Rolling Arrays (Space-Optimized DP)
When dp[i] depends on dp[i-1] only, use 1D array instead of 2D. Reduce O(n²) to O(n) or O(n) to O(1).
3
Iterative vs Recursive
Recursive solutions use call stack (O(depth) space). Iterative versions often use O(1) space. Convert recursion to iteration when possible.
4
Choose Right Data Structure
Adjacency list (O(V+E)) vs adjacency matrix (O(V²)). Linked list vs array. The right choice saves both time and space.
💡 Key Takeaways
- → Space complexity is often as important as time complexity, especially in memory-constrained environments.
- → Auxiliary space ≠ total space. Auxiliary space excludes input storage.
- → There's usually a time-space tradeoff: faster algorithms often use more memory.
- → Stack space matters! Deep recursion can cause stack overflow in languages with limited call stack.