0

while accessing all elements of a matrix we can use to for loops and time complexity is O(n^2). But, when we are only accessing rows from a 2D array, what is the time complexity? Is it O(n) when n = number of rows? Ex:- 

int arr[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
for (int i = 0; i < arr.length; i++) 
  for (int j = 0; j < arr[0].length; j++)

The time complexity for the above lines is O(n^2).

But if we access the matrix in the following way will the time complexity still be O(n^2) or will it be O(n)

for (int rows[] : arr) - Time complexity is O(n) or O(n^2)
Newbie
  • 2,664
  • 7
  • 34
  • 75
  • 1
    That loop will only run `rows` times so unless you're doing something complicated within it, it's `O(rows)`. Assuming `rows=cols`, it's `o(n)` – Maria Ines Parnisari Jun 07 '17 at 02:48
  • I feel like closing this as a duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) You're trying to see something in the code which conflicts with how you calculate big O. The only exception would be a language that makes deep copies of the objects used in for-each loops, which I'm not sure even exists (Java definitely doesn't do that). – Bernhard Barker Jun 07 '17 at 07:48

2 Answers2

0

If you are going to iterate all cells for each row, so it still be O(n^2). There is no real difference between those two methods when considering run time.

LiorP
  • 94
  • 4
0
int arr[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
for (int i = 0; i < arr.length; i++) 
  for (int j = 0; j < arr[0].length; j++)

This is having complexity of O(n) and not O(n^2). That is you are traversing and seeing n items only once and the it linearly increases when n increases.

Nithin Devang
  • 69
  • 1
  • 8