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.

I use a pointer which have the address of the next array to connect them. — jizhihaoSAMA
– jizhihaoSAMA, Commented Mar 25, 2020 at 10:06

Mikhail · Accepted Answer · 2020-03-25 09:59:17Z

4

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.

answered Mar 25, 2020 at 9:59

Mikhail

22.1k8 gold badges83 silver badges160 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

jizhihaoSAMA Over a year ago

If I have three special arrays,each array has the address of next array.(Think it as a Linked List),So now If I iterate it,the time complexity will be O(n),right?So does this faster than a normal 3D array?

nits.kk Over a year ago

again, suppose you have array AddrArray of size N so there will be N iteration , now if each of the arrays to whose address the AddrArray points to have equal size M then the total time complexity is of the order N*M. You need to ask first question or understand from the context "what is N (or M or K...)?". then the resultant time complexity will make sense.

possum · Accepted Answer · 2020-03-25 09:52:51Z

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.

answered Mar 25, 2020 at 9:52

possum

2,9667 gold badges19 silver badges24 bronze badges

Comments

noelicus · Accepted Answer · 2020-03-25 09:57:38Z

1

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).

answered Mar 25, 2020 at 9:57

noelicus

15.1k4 gold badges96 silver badges116 bronze badges

Comments

nits.kk · Accepted Answer · 2020-03-25 10:04:31Z

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.

Collectives™ on Stack Overflow

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

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related