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 1s and 0s. The function then returns how many 1s there are.

So take a look at 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 1s.

Here’s the function:

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