A Common-Sense Guide to Data Structures and Algorithms

O(log N) Explained

Let’s bring this all back to Big O Notation. Whenever we say O(log N), it’s actually shorthand for saying O(log₂ N). We’re just omitting that small 2 for convenience.

Recall that O(N) means that for N data elements, the algorithm would take N steps. If there are eight elements, the algorithm would take eight steps.

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

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

This is exactly what happens with binary search. As we search for a particular item, we keep dividing the array’s cells in ...