Search code examples
pythonalgorithm

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

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

    If you define n as max(len(outer_array), len(inner_array)), you can describe the algorithm as O(n^2) complexity.

    So in essence, it depends on your definition of n, as mentioned before.