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

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