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?

Furring

What´s n in your case? The code shows the array of sizes 9. If, actually, you work with NxN array the complexity is O(N**2). And, please, format your code – Platter

n : number of input size will be 81 number of array[9][9] elments – Furring

Well, if n == N*N where N is a size of an each array as well as the number of arrays, then O(N**2) == O(n); however, IMHO, the parameter n as it defined (n == N*N) is quite strange. – Platter

The 'complexity' only shows to you how fast your work grows comparing with the rate of growing the input size. This means that it looks different depending upon what you take as input size - say, number of elements in array or row/column count. Just like measuring one thing in meters or feet gives "different" results. – Asdic

this nested loop for one array one for Travers rows and second loop for columns so i want to Travers all element in one array .. so why O(n) not correct – Furring

Having said this, I should note that under such circumstances people usually choose O(N*M) and for a good reason: many algorithms are unsymmetric. – Asdic

@AhmedIsmail:- Why do you think it will be O(n) when you are traversing for every row all the columns ie, your for every row your second for loop will traverse 9 times to traverse each column. So for row1, 9 times for column then row 2, 9 times ....and similarly row9, 9 times making it traverse 9*9 = 81 times ie, n*n = n^2 times – Obscenity

Attempt to rephrase OP's question: Whether you represent the data as a two dimensional array, or a single dimensional linear array, you have the same input data size, 81 elements, and each element is only traversed once. Then why is the O() represented as a square and not linear? Is O() dependent on the shape of the input data structure? – Wychelm

There is nothing wrong with calling the whole size of the pxq matrix n=pq. But if you insist on the size being 9x9, your complexity is O(1). – Banville

@Rahul Tripathi the size of array is fixed can this nested loop be O(1) as Marc Glisse said ? – Furring

@Wychelm It's dependent upon the way the problem is formulated. The complexity is just an abstraction. It measures the conditional growth rate. If you say O(n) you really mean that the amount of work grows linear while the total number of elements in array grows linear. Usually it's much less useful than O(n*m) but it's correct as long as you really understand what you say. – Asdic

@AhmedIsmail:- I think the whole summary has been given by the comment given by @ user4419802 – Obscenity

Marc Glisse can you measure complexity after edit for the whole function ? – Furring

@Ahmed Do NOT change your questions to different questions. If you have a new question, ask a new question. – Superpose

@user4419802 can you help me to measure time complexity for whole function ? – Furring

@AhmedIsmail First of all do indent all the lines and count the braces. As far as I see your code is wrong. – Asdic

@AhmedIsmail Next, as you were said, as your function still accepts a fixed size input only it's complexity is a constant. – Asdic

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.

Superpose

Your answer was very informative, but I want to double-check your logic. My use case is an object, where every key has an array of different lengths. for example: { a: [1,2,3], b: [1], c: [1,2,3,4,5] }. I want to sum all the values in the arrays (in this example 22) so I need to iterate over every key and iterate over every element in that keys array. Would you consider this O(n * m) where n is the number of keys, and m represents the lengths of all arrays? I am stuck in this scenario because the arrays are of different lengths. – Victoria

Answer 2

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.

Obscenity

n : number of input size will be 81 number of array[9][9] elements – Furring

@AhmedIsmail:- Both the arrays in your case are getting iterated for 9 times ie, n and m both are equal, so its going to be O(n*n) = O(n^2) – Obscenity

Rahul Tripathi can you measure complexity after edit for the whole function ? – Furring

so if the input size are fixed time complexity will be O(1) ie. number of time will operations executed ? – Furring

@AhmedIsmail I don't think you quite understand the idea of big Oh. – Sharell

Answer 3

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)

Wychelm

but in my case : two nested loop are use to traverse all the element and n : number of input size will be 81 number of array[9][9] elements so why should n't O(n) ? – Furring

This answer is false. Neither n nor m are the size of the actual input (let's say N). Given n in this scenario, it logically follows that m = N/n and the actual complexity is O(n * (N/n)) = O(N). – Alpestrine

@Nit logically follows that m = N/n. Correct, which means N=m*n So your answer O(N) becomes O(m*n). Your answer is the same as mine. – Wychelm

@Wychelm n * (N/n) = n * m = N. The complexity for all of these is still O(N), that is, linear with the original input size. – Alpestrine

@NIT That really depends on how you're quantifying your data size. If I ask you how big your data size is, and you respond with n then the amount of time to do your computation is proportional to n^2 or nxm. If you respond with N then, yes computation time is proportional to N. Neither is less valid than the other. – Wychelm

@Wychelm Big-O notation always corresponds to the input data size, it doesn't matter how you annotate it. The complexity is O(n) or O(N), regardless of whether you choose the name of the variable to be n or N. – Alpestrine

Answer 4

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.

Hellespont

Answer 5

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.

Affinitive

Answer 6

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

Kolodgie

This is an incredibly misleading answer. – Sharell

Which part is misleading? – Kolodgie

@JatinderPal It's when you considered n to be i times j, then complexity will be O(n). You could just simply say complexity is i * j – Replicate

That will complexity O(i * j), and if i = j, it will be O(i^2). Is misleading in the sense that usually when someone says O(n), it means linear time, whereas O(i * j) is quadratic when i = j. – Burkhalter