O(log N) Explained

Let’s bring this all back to Big O notation. In computer science, whenever we say O(log N), it’s actually shorthand for saying O(log₂ N). We just omit that small 2 for convenience.

Recall that Big O notation resolves the key question: if there are N data elements, how many steps will the algorithm take?

O(log N) means that for N data elements, the algorithm would take log₂ N steps. If there are 8 elements, the algorithm would take three steps, since log₂ 8 = 3.

Said another way, if we keep dividing the 8 elements in half, it would take us three steps until we end up with 1 element.

This is exactly what happens with binary search. As we search for a particular item, we keep dividing the array’s cells in half until we narrow it down to the correct number.

Said simply: O(log N) means the algorithm takes as many steps as it takes to keep halving the data elements until we remain with 1.

The following table demonstrates a striking difference between the efficiencies of O(N) and O(log N):

While the O(N) algorithm takes as many steps as there are data elements, the O(log N) algorithm takes just one additional step each time the data is doubled.

In future chapters, you’ll encounter algorithms that fall under categories of Big O notation other than the three you’ve learned about so far. But in the meantime, let’s apply these concepts to some examples of everyday code.