A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

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:

function countOnes(outerArray) {
  let count = 0;

  for (const innerArray of outerArray) {
    for (const number of innerArray) {
      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, ...