What is the complexity of a while loop?

Question

I have below code.Where, I have to print the matrix in zigzag fashion

arr3 = [
[1, 2, 3, 4],
[5, 6, 7, 8],
['a', 'b', 'c', 'd'],
['X', 'Y', 'Z', 'N']
]
def zigZagMatrix(arr, n, m):
 i_prev = 0
 j_prev = 0
 i = 0
 j = 0
 done = False
 while not done:
 while i >= 0 and j < m:
 print(arr[i][j])
 i -= 1
 j += 1
 if i == n-1 and j > m-1:
 done = True
 i_prev += 1
 if i < n-1 and i_prev < n:
 j = 0
 else:
 j_prev += 1
 j = j_prev
 if i_prev >= n:
 i = n - 1
 else:
 i = i_prev
zigZagMatrix(arr3, 4, 4)

To me it looks like O(n), because we have to traverse though the entire array, but there is an another while loop which does run until the condition fails. So, I am really confused. Whether it would be O(n) or O(n) + O(m) or something else

• Karan Shah: I think it should be O(n)

Answer 1

Assuming the code is correct and every element of the matrix is printed once then the complexity of the double while loop is the number of elements that are printed. Because you have an n×ばつm matrix you have n×ばつm elements to be printed. This means that the complexity would be O(n×ばつm).

(削除) However, I have tested the code and it never seems to reach the stopping condition. The program just keeps iterating forever. This means that, in its current version, the complexity is not defined. If anything, it would be infinite. (削除ここまで)

• Rasmi Ranjan Nayak: Thanks for pointing out for never reaching stopping condition. I have changed the code.