Multi-dimensional arrays in C Sharp (C#) - Time & Space Complexity

Time Complexity: Multi-dimensional arrays

O(rows * cols)

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 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.

int[,] matrix = new int[rows, cols];
for (int i = 0; i < rows; i++)
{
    for (int j = 0; j < cols; j++)
    {
        matrix[i, j] = i + j;
    }
}
    

This code fills every element in a two-dimensional array by looping through each row and column.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops accessing each element in the 2D array.
• How many times: The inner loop runs once for each column, and the outer loop runs once for each row, so total operations equal rows x cols.

How Execution Grows With Input

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

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

Pattern observation: Doubling both rows and columns causes the total operations to grow by four times, showing a multiplication effect.

Final Time Complexity

Time Complexity: O(rows * cols)

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

Common Mistake

[X] Wrong: "The time complexity is O(rows + cols) because there are two loops."

[OK] Correct: The loops are nested, so for each row, all columns are processed, multiplying the work instead of adding it.

Interview Connect

Understanding how nested loops over multi-dimensional arrays affect time helps you explain and optimize code that deals with grids, tables, or images.

Self-Check

"What if we changed the inner loop to only run half the columns? How would the time complexity change?"