What log n means
log n is how many times you can cut n in half before 1 is left. 1,000 halves to 1 in about 10 cuts, 1 million in about 20, and 1 billion in about 30. That's why "O(log n)" is almost as good as instant.
In plain words
A friend thinks of a number from 1 to 100. You guess 50. "Higher." You guess 75. "Lower." 62... Every answer throws away half of what's left. You'll find it in at most 7 guesses, because 100 halves down to 1 in 7 steps.
Now make it 1 to 1 million. It feels like it should take forever, but it's only 20 guesses. Double the numbers to 2 million: just 1 more guess. That's the magic of log: making the problem twice as big only adds one step.
Examples
- A paper dictionary with 100,000 words: about 17 flips to find any word.
- git bisect over 1,000 commits: about 10 test runs to find the one that broke the build.
- A database index over 1 billion rows: about 30 comparisons (and only 3 or 4 disk reads, because each B+tree page splits hundreds of ways, not 2).
- A heap with 1 million items: adding one takes at most about 20 swaps.
- A balanced tree of height h holds about 2ʰ items, so height = log₂(items).
Watch it: halving 16 cards
Watch it: guessing a number from 1 to 1,000,000
How many steps?
| Items | Halvings (log n) | Check every item (n) |
|---|---|---|
| 8 | 3 | 8 |
| 1 thousand | about 10 | 1 thousand |
| 1 million | about 20 | 1 million |
| 1 billion | about 30 | 1 billion |
Compare everything with everything (n²) for 1 million items: a million million steps (a trillion), versus 20 steps.
See the gap
Steps for 100 items, drawn to scale.
Steps for 1 million items, drawn to scale.
At 1 million, the log n bar is 50,000 times shorter than the n bar: too thin to see. The bigger the data, the bigger the win.
Where log n shows up
| Binary search | Halve the sorted list each step. |
| Balanced tree, B+tree index | Each level splits the data; the height is log n. |
| Heap push and pop | An item moves up or down one level per swap; log n levels. |
| Merge sort (n log n), quick sort (n log n on average) | log n levels of splitting, n work on each level. |
| Union-find (nearly constant) | Grows even slower than log n, so treat it as O(1). |
How to spot it in code
- A loop where the size is divided by 2 (or any fixed number) each time:
while (n > 1) n = n / 2. - A loop where something doubles until it reaches n:
for (let i = 1; i < n; i *= 2). - Recursion that goes into only ONE half each call (binary search). If it goes into BOTH halves and does n work to combine, that's n log n (merge sort).
The code behind the animations (JavaScript, tested)
// How many times can you halve n before 1 is left? That count is log2(n), rounded up.
function halvings(n) {
let steps = 0;
while (n > 1) {
n = Math.ceil(n / 2);
steps++;
}
return steps;
}
// Binary search over the numbers 1..n, counting the guesses. Never more than halvings(n) + 1.
function guessCount(n, secret) {
let lo = 1, hi = n, guesses = 0;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
guesses++;
if (mid === secret) return guesses;
if (mid < secret) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}Things people get wrong
- The base doesn't matter in Big O: log₂ n and log₁₀ n differ only by a fixed factor (about 3.3), so everyone just writes log n.
- log n needs a shortcut to throw away half: sorted data, a tree shape, a yes/no question that flips once. Unsorted data has no shortcut, so searching it is O(n).
- O(log n) is not "slow-ish O(n)". At 1 billion items, it's 30 steps versus 1 billion.
The other "log"
In system design, a log means something different: a list of events you only ever add to the end of, in order, like a bank statement. Kafka, a database's write-ahead log and the outbox table are all logs in this sense. Nothing to do with log n.