Time Complexity: Two-dimensional arrays
O(n * m)
0
0
Two-dimensional arrays in Java - Time & Space Complexity
Understanding Time Complexity
When working with two-dimensional 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 operations changes when we loop through all elements in a 2D array.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
int[][] matrix = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = i + j;
}
}
This code fills every element in a two-dimensional array with the sum of its row and column indices.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Assigning a value to each element in the 2D array.
- How many times: The inner loop runs m times for each of the n iterations of the outer loop, so n x m times in total.
How Execution Grows With Input
As the number of rows (n) and columns (m) increase, the total operations grow by multiplying these two sizes.
| Input Size (n x m) | Approx. Operations |
|---|---|
| 10 x 10 | 100 |
| 100 x 100 | 10,000 |
| 1000 x 1000 | 1,000,000 |
Pattern observation: Doubling both dimensions causes the operations to increase by four times, showing a growth proportional to the product of n and m.
Final Time Complexity
Time Complexity: O(n * m)
This means the time to complete the task grows proportionally to the total number of elements in the two-dimensional array.
Common Mistake
[X] Wrong: "The time complexity is O(n) because there is an outer loop running n times."
[OK] Correct: The inner loop also runs m times for each outer loop iteration, so the total work depends on both n and m multiplied together, not just n.
Interview Connect
Understanding how nested loops over two-dimensional arrays affect time helps you explain and reason about performance clearly in interviews.
Self-Check
"What if the inner loop only ran up to a fixed number instead of m? How would the time complexity change?"