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