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

O(log N) Explained

Let’s bring this all back to Big O notation. In this book, whenever we say O(log N), imagine that we’re saying O(log₂ N). In ​Ignoring Constants​, we’ll discuss why we’re dropping the base of 2 in our notation. But for now, when you see O(log N), treat it in your mind as O(log₂ N).

With this in mind, we can now explain precisely what O(log N) means.

Recall that Big O notation resolves the key question: if there are N data elements, how many steps will the algorithm take?

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

Said another way, if we keep dividing the 8 elements in half, it would take us three steps until ...