What is the time complexity of traversing a 2d array

Question

What is the time complexity of traversing (rows ,columns) a two dimensional array?

bool check(int array [9][9])
{ 
    int num=0;
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) { 
            if (array [i][j] == 0) {        
                num++;
            }
        }
    }
    return num;
}

I think each for loop will take square root of n so that nested loops totally take O(n) as traversing all elements, where I am defining n as the total size of the input (in this case 81 elements in array). Is that correct?

Answer 1

As you define n to be the total size of the input, yes the running time of the algorithm you propose will be O(n): you are performing one single operation on each element of the input, for n total operations.

Where the confusion is arising from this question is that by convention, multi-dimensional arrays are not referred to by their total size but rather by each of their dimensions separately. So rather than viewing array as being of size n (81) it would be considered to be an array of size p x q (9 x 9). That would give you a running time of O(pq). Or, if we limit it to square arrays with both dimensions r, O(r^2).

All are correct, which is why it's important to give a clear definition of your variables up front when talking about time complexity. Otherwise, when you use n to mean the total size when most people would assume that n would be a single dimension, you are inviting a lot of confusion.

Answer 2

For any algorithm of the form

for (1..n) {
    for (1..m) { 
        doSomething();
    }
}

The average, best and worst case time complexity is O(n x m). In your case if n=m, it becomes O(n^2)

Answer 3

The time complexity will be O (n*m) where n the number of arrays which is the 1st dimension and m the max size of each internal array ie, the 2nd dimension.