Two-dimensional arrays in C - Time & Space Complexity

Time Complexity: Two-dimensional arrays

O(rows * cols)

Understanding Time Complexity

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

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        process(array[i][j]);
    }
}
    

This code goes through every element in a two-dimensional array and processes it once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop processes each element in a row.
• How many times: The inner loop runs cols times for each of the rows iterations of the outer loop.

How Execution Grows With Input

As the number of rows and columns grow, the total operations 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 multiplies the work by four, showing a growth proportional to the product of rows and columns.

Final Time Complexity

Time Complexity: O(rows * cols)

This means the time to complete grows directly with the total number of elements in the two-dimensional array.

Common Mistake

[X] Wrong: "The time complexity is just O(rows) or O(cols) because there are two loops but only one matters."

[OK] Correct: Both loops run fully and multiply the total work, so the total time depends on both dimensions together, not just one.

Interview Connect

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

Self-Check

"What if we only looped through half the columns in each row? How would the time complexity change?"