Course contentsShow
← Computer Science
Lesson 311 of 2,8727. Introduction to Complexity AnalysisFree lesson

Analyzing Multi-Dimensional Space

Computing space complexity for algorithms using matrices and multidimensional arrays.

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.