$O(\log N)$ is often the most confusing complexity for students, because logarithms feel abstract. The key insight is concrete and mechanical.
The "Halving" Rule
Whenever an algorithm cuts the problem space in half at each step, it is $O(\log N)$. The base of the logarithm (base 2 for binary halving) is a constant and gets dropped per Rule 1.
Example — Binary Search on a sorted array of 1,024 elements:
| Step | Remaining Elements |
|---|---|
| 1 | 1,024 |
| 2 | 512 |
| 3 | 256 |
| 4 | 128 |
| 5 | 64 |
| 6 | 32 |
| 7 | 16 |
| 8 | 8 |
| 9 | 4 |
| 10 | 2 |
| 11 | 1 — found it |
1,024 elements required only 11 steps. If you doubled the array to 2,048 elements, it would take just 12 steps — one more. That's the power of logarithmic growth.
The Inverse of Exponential
$\log_2 N$ answers the question: "How many times do I have to halve N before I reach 1?" For $N = 1{,}000{,}000{,}000$, the answer is about 30. This is why $O(\log N)$ algorithms scale to enormous inputs with ease.
Code pattern that signals $O(\log N)$: Any loop or recursion where the index is multiplied or divided (not incremented) each step — i *= 2, i /= 2, mid = (lo + hi) // 2.