What's the time complexity of using for loop to iterate 2D array?

Question

In this answer,it said that:

An algorithm is said to run in linear time if its time execution is directly proportional to the input size, i.e. time grows linearly as input size increases.

I have input a 3x3 array.So I need to input 9 numbers.It need 9 times to iterate.

I have input a 4x4 array.So I need to input 16 numbers.It need 16 times to iterate.

........

The execution of iteration is directly proportional to the amount of numbers(or the size). So I think the time complexity should be O(n).

But another answer said that:

O(n^c): Time complexity of nested loops is equal to the number of times the innermost statement is executed. For example the following sample loops have O(n^2) time complexity

for (int i = 1; i <=n; i += c) {
   for (int j = 1; j <=n; j += c) {
      // some O(1) expressions
   }
}

I feel a little confused. So I think the question can also be:

What is the mean of n in array?(Does it means the size of the array or the dimension of the array?)What's the time complexity of use for loop to iterate 2D array. Is it O(n) or O(n^2)?

If the time complexity is O(n^2) due to it have two for loops. I use this to create a 3x3 array:

a[0,1,2] -> b[0,1,2] -> c[0,1,2]

So I use it to iterate this arrays.It will be O(n),So it will faster than using for loop to iterate the arrays.Why?

PS:I use Google translation to see those answer,so maybe I misunderstand it.

Answer 1

What is the mean of n in array? (Does it means the size of the array or the dimension of the array?)What's the time complexity of use for loop to iterate 2D array. Is it O(n) or O(n^2)?

You are exactly correct. This is a matter of convention. It is important what n denotes in a particular problem.

In case our array is arr[n][n], iteration takes O(n^2) time. In case our array is arr[k][k] and n=k*k is the size of the array, iteration takes O(n) time. There is no contradiction here since we defined n differently in those cases.

Generally, if you only access an array element once, it is said that you have a linear complexity. No matter how you express this with the O notation.

Answer 2

The complexity for the nested for loop is indeed n^2 and not n. n in array there is the size.

Maybe something to think about to help you: Consider if we needed to iterate over two different arrays in a similar manner and the arrays have different sizes of m and n, e.g.

for (int i = 1; i <=n; i += c) {
   for (int j = 1; j <=m; j += c) {
      // some O(1) expressions
   }
}

This would be O(m*n). The case you're asking about is a specialization of this.

Answer 3

For a 4x4 2D array manipulation if your input was only 4 it would be of exponential complexity. If you're input was all 16 numbers then it's linear. It all comes down to what you're passing in.

In your example if n is your input size then the fact you have a nested iteration makes it O(n^2).

Answer 4

First of all for the question to be answered is "what is n ?".

If you have input a 3x3 array.So you need to input 9 numbers.It need 9 times to iterate. If you have input a 4x4 array.So you need to input 16 numbers.It need 16 times to iterate

Now if n = 3 & 4 for above two cases respectively then time to iterate is proportional to n square. If n = 9 & 16 for the above cases respectively then it is proportional to n.

Now coming to nested loops.

For an array of size [ROW][COL]

for (int r= 0; r < ROW; r++){ //outer loop
    for(int c= 0; c<COL; c++){ // inner loop
        //process array[r][c]
    }
}

For each iteration of outer loop , we have COL iterations of inner loop. Outer loop iterates for ROW number of times , hence time complexity is of the order ROW multiplied by COL.

Hope this helps.