An Algorithm of the Third Kind

In the previous chapter, we learned that binary search on an ordered array is much faster than linear search on the same array. Let’s learn how to describe binary search in terms of Big O Notation.

We can’t describe binary search as being O(1), because the number of steps increases as the data increases. It also doesn’t fit into the category of O(N), since the number of steps is much fewer than the number of elements that it searches. As we’ve seen, binary search takes only seven steps for an array containing one hundred elements.

Binary search seems to fall somewhere in between O(1) and O(N).

In Big O, we describe binary search as having a time complexity of:

O(log N)

I pronounce this as “Oh of log N.” This type of algorithm is also known as having a time complexity of log time.

Simply put, O(log N) is the Big O way of describing an algorithm that increases one step each time the data is doubled. As we learned in the previous chapter, binary search does just that. We’ll see momentarily why this is expressed as O(log N), but let’s first summarize what we’ve learned so far.

Of the three types of algorithms we’ve learned about so far, they can be sorted from most efficient to least efficient as follows:

O(1)

O(log N)

O(N)

Let’s look at a graph that compares the three types.

Note how O(log N) curves ever-so-slightly upwards, making it less efficient than O(1), but much more efficient than O(N).

To understand why this algorithm is called “O(log N),” we need to first understand what logarithms are. If you’re already familiar with this mathematical concept, you can skip the next section.