O'Reilly logo

A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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(log2 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 log2 N steps. If there are eight elements, the algorithm would take three steps, since log2 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required