CODEWITHSUNDEEP
c++arraysalgorithmfor-looptime-complexity
Ahmed Mano
Ahmed Mano

Reputation: 135

What is the time complexity of traversing a 2d array

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?

Upvotes: 9

Views: 38469

Answers (6)

VIKRAM SINGH CHOUHAN
VIKRAM SINGH CHOUHAN

Reputation: 65

The Time complexity is derived by how many times your code is going to do lookup of an element in the data structure to deduce the result. It does not matter whether it is 1-D, 2-D or n-D array. If you access an element not more than once for an n-D array to deduce the solution, the complexity is linear O(N), where N = N1 * N2 * ... *Nn

Let's understand this by taking real world example of two different hotels having N rooms each. You need to search your friend in the hotel. In first scenario let's say first hotel has 100 rooms on single(ground) floor, you need to visit 100 rooms in worst case to find your friend, so here complexity is linear i.e. 0(N) or O(100). In second scenario the hotel has 4 floors having 25 rooms each. In the worst case you have to visit 25*4=100 rooms (ignore the accessing time/process between floors), hence complexity is again linear.

Upvotes: 1

Ashish
Ashish

Reputation: 71

The time complexity is O(N), which means its time complexity is linear. Let's look at the concept of time complexity. When we define any time complexity in Big O notation what we mean is how does the graph of N versus run time must look like in the worst execution case.

For given nested loop size of the data is 9*9 = 81.No matter what operation you perform in the inside for loop. The loops will not execute more than 9*9 = 81 times. If the size of the array was [10][10] the loops will execute not more than 100 times.

If you make graph of execution time of the code with number of inputs or data it will be linear.

Upvotes: 5

Jatinder Pal
Jatinder Pal

Reputation: 729

A 2-d array arr[i][j] can be traversed by a single loop also, where the loop will run for (i × j) times.

Consider n = (i×j), then the time complexity for traversing a 2-d array is O(n).

Thanks to coder2design.com

Upvotes: -1

Barry
Barry

Reputation: 302807

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.

Upvotes: 31

RaGe
RaGe

Reputation: 23657

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)

Upvotes: 8

Rahul Tripathi
Rahul Tripathi

Reputation: 172408

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.

Upvotes: 8

Related Questions