What is Big O in this example of code, O(N) or O(N^2)?

Can you please explain what is Big O in this example of code?

arr = [
  [1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1],
  [1, 1]
]

def count_ones(outer_array):
  count = 0
  for inner_array in outer_array:
    for number in inner_array:
      count += 1
  return count

count_ones(arr)

Answer

It depends entirely on your definition of n. If you define n to be the number of cells in the 2d matrix, then this nested loop is of linear complexity O(n) in relation to it.

On the other hand, if you define n to be the length of the outer array and m the maximum length of the inner arrays then the time complexity is O(n*m).

Either way, the complexity can’t be O(n^2) since in that case it needs to be a square matrix with sides of equal length n.