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)

CodePudding user response：

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.

CodePudding user response：

Given that n is defined as the total number of elements in the nested array:

  for inner_array in outer_array:
    for number in inner_array:

is O(n) since it visits every element once.

count  = 1

is O(1) since it is basic arithmetic.

O(1) * O(n) = O(n)

CodePudding user response：

Basically, you have 2-dimension array and every element picks once. In common case it's O(N), where N - number of elements.