A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Count the Ones

Here’s another algorithm where the Big O is different from what it seems at first glance. This function accepts an array of arrays, where the inner arrays contain 1’s and 0’s. The function then returns how many 1’s there are.

So, for this example input:

[
  [0, 1, 1, 1, 0],
  [0, 1, 0, 1, 0, 1],
  [1, 0]
]

our function will return 7, since there are seven 1’s. Here’s the function in Python:

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

What’s the Big O of this algorithm?

Again, it’s easy to notice the nested loops and jump to the conclusion that it’s O(N²). However, the two loops are iterating over two ...