Multidimensional arrays in PHP - Time & Space Complexity

Time Complexity: Multidimensional arrays

O(n * m)

Understanding Time Complexity

When working with multidimensional arrays, it is important to understand how the time to process them grows as the array size increases.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];

foreach ($matrix as $row) {
    foreach ($row as $value) {
        echo $value . " ";
    }
}

This code loops through a 2D array (a matrix) and prints each value.

Identify Repeating Operations

• Primary operation: Nested loops over rows and columns of the array.
• How many times: Outer loop runs once per row, inner loop runs once per element in each row.

How Execution Grows With Input

As the number of rows and columns grows, the total steps grow by multiplying these sizes.

Input Size (rows x columns)	Approx. Operations
10 x 10	100
100 x 100	10,000
1000 x 1000	1,000,000

Pattern observation: The total operations grow by the product of rows and columns, so doubling both makes the work much larger.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the number of rows times the number of columns in the array.

Common Mistake

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

[OK] Correct: Each element in every row is visited, so the total steps multiply, not add. The nested loops multiply the work.

Interview Connect

Understanding how nested loops affect time helps you explain and optimize code that works with tables, grids, or matrices in real projects.

Self-Check

"What if the inner arrays had different lengths? How would the time complexity change?"