Let’s bring this all back to Big O Notation. Whenever we say O(log N), it’s actually shorthand for saying O(log_{2} 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_{2} N steps. If there are eight elements, the algorithm would take three steps, since log_{2} 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 ...

Start Free Trial

No credit card required