[Python] Why is the worst case complexity not O(N^2) for this code snippet? [duplicate]

I came across this Python code snippet in the book A Common-Sense Guide to Data Structures and Algorithms: Level Up Your Core Programming Skills.

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


The explanation for the worst case complexity of this code is reasoned as follows in the books :

Again, it’s easy to notice the nested loops and jump to the conclusion that it’s O(N2). However, the two loops are iterating over two completely different things. The outer loop is iterating over the inner arrays, and the inner loop is iterating over the actual numbers. At the end of the day, our inner loop only runs for as many numbers as there are in total. Because of this, we can say that N represents how many numbers there are. And since our algorithm simply processes each number, the function’s time complexity is O(N).
​

I am unable to wrap my head around it. How can it be simplified to O(N) when it is guaranteed that we need to perform N comparisons within the inner loop in the worst case ? I could only arrive at a complexity of O(N*M) to the best of my understanding.

Continue reading...