Analyzing Multi-Dimensional Space
You'll learn: How to calculate the space complexity of algorithms that use matrices and multidimensional arrays.
The Core Idea
When your algorithm uses 2D arrays (matrices), 3D arrays, or higher-dimensional structures, the space they occupy grows multiplicatively with their dimensions. A single-dimensional array of size n uses O(n) space, but a 2D array with n rows and m columns uses O(n × m) space.
Think of it like building storage: a shelf (1D array) holds items in a line. A bookcase (2D array) has shelves stacked vertically—multiply rows by items per row. A warehouse (3D array) has multiple bookcases—multiply depth by rows by items.
How to Analyze
For a 2D array with dimensions n × m:
- Total cells = n × m
- Space complexity = O(n × m)
For a 3D array with dimensions n × m × p:
- Total cells = n × m × p
- Space complexity = O(n × m × p)
Square matrices (n × n) simplify to O(n²) because both dimensions are the same.
Common Patterns
- Fixed-size 2D array (e.g., 10×10 grid): O(1) — constant space, dimensions don't depend on input
- Dynamic matrix (e.g., n×n): O(n²) — grows quadratically
- Rectangular matrix (e.g., n×m): O(n × m) — grows with both dimensions
- Array of arrays with varying sizes: Analyze total elements across all nested arrays
Real Example
An algorithm storing an n×n game board uses O(n²) space. If you also store a separate 1D array of size n for player scores, total space is O(n²) + O(n) = O(n²) (the quadratic term dominates).
Key Takeaway: Multidimensional array space complexity multiplies dimensions together; for matrices, remember O(n²) for square and O(n × m) for rectangular.