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 ...
Get A Common-Sense Guide to Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
