An Algorithm of the Third Kind

In the previous chapter, you learned that binary search on an ordered array is much faster than linear search on the same array. Let’s now look at 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 N data elements. As we have seen, binary search takes only seven steps for an array containing 100 elements.

Binary search, then, seems to fall somewhere in between O(1) and O(N). So what is it?

In Big O terms, 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 you learned in the previous chapter, binary search does just that. You’ll see momentarily why this is expressed as O(log N), but let’s first summarize what you’ve learned so far.

The three types of algorithms you’ve learned about so far 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 upward, making it less efficient than O(1) but much more efficient than O(N).

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