Multi-dimensional arrays in C++ - Time & Space Complexity

Time Complexity: Multi-dimensional arrays

O(n * m)

Understanding Time Complexity

When working with multi-dimensional arrays, it is important to understand how the time to process them grows as their size increases.

We want to know how the number of operations changes when we access or loop through all elements in these arrays.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int matrix[3][4] = {0};
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 4; j++) {
        matrix[i][j] = i + j;
    }
}
    

This code fills a 3 by 4 matrix with the sum of its indices.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop writes to each element of the matrix.
• How many times: The inner loop runs 4 times for each of the 3 outer loop iterations, totaling 12 times.

How Execution Grows With Input

Imagine the matrix size changes to n rows and m columns. The total operations grow as the product of n and m.

Input Size (n x m)	Approx. Operations
3 x 4	12
10 x 10	100
100 x 100	10,000

Pattern observation: Doubling both dimensions roughly quadruples the operations because you visit every element.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the total number of elements in the multi-dimensional array.

Common Mistake

[X] Wrong: "The time complexity is O(n) because there is only one loop inside another."

[OK] Correct: Each loop multiplies the work. The inner loop runs completely for every outer loop iteration, so total work is the product, not just one loop's size.

Interview Connect

Understanding how nested loops over multi-dimensional arrays affect time helps you explain and optimize code clearly in interviews.

Self-Check

"What if the inner loop size depends on the outer loop index (e.g., j runs from 0 to i)? How would the time complexity change?"