A Common-Sense Guide to Data Structures and Algorithms, Second Edition: "Count the Ones"-should not be O(N^2)? (page 102)

p102_Count_the_Ones787×981 60.8 KB

Hello,

Can you please check the time complexity of “Count the Ones” on page 102? I got confused. It has 2 loops (outer and inner). Let’s say I have an array of arrays like below with 10 outer and 10 inner:

[
[1,2,3,4,5,6,7,8,9,10],
[1,2,3,4,5,6,7,8,9,10],
[1,2,3,4,5,6,7,8,9,10],
[1,2,3,4,5,6,7,8,9,10],
[1,2,3,4,5,6,7,8,9,10],
[1,2,3,4,5,6,7,8,9,10],
[1,2,3,4,5,6,7,8,9,10],
[1,2,3,4,5,6,7,8,9,10],
[1,2,3,4,5,6,7,8,9,10],
[1,2,3,4,5,6,7,8,9,10]
]

— code:
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

If I use the code from the book then it should run 10^2 = 100 steps, is not it?
Loop 1: 1st outer array with 10 inner array values
Loop 2: 2nd outer array with 10 inner array values
…
Loop 10: 10th outer array with 10 inner array values

10+10+10…+10 = 100

Thanks!