One question
Take a million. Cut it in half. Cut that in half. Keep going.
How many cuts until you are down to one?
Have a guess, then press play.
Start. Start with 1,000,000. How many times can it be cut in half before it gets down to 1?
- Halvings so far
- 0
- Value now
- 1,000,000
Twenty. A million becomes one in twenty halvings.
That is all a logarithm is. The logarithm base 2 of a number answers: how many times do I halve this to reach 1? It is written log₂.
log₂ of 1,000,000 is about 20.
The other way round: doubling
Run it backwards and the same number appears. Start at 1 and double:
1, 2, 4, 8, 16, 32, 64, ...
After 10 doublings you are at 1,024. After 20, just over a million. After 30, just over a billion.
So a logarithm undoes a power.
- 2 to the power 10 is 1,024. So log₂ of 1,024 is 10.
- 2 to the power 20 is about a million. So log₂ of a million is about 20.
"How many doublings to get there?" and "how many halvings to get back?" are the same question.
Why it grows so slowly
Try the other starting values in the demo and compare.
| n | log₂ n |
|---|---|
| 16 | 4 |
| 1,024 | 10 |
| 1,000,000 | about 20 |
| 1,000,000,000 | about 30 |
| 1,000,000,000,000 | about 40 |
From a thousand to a million, the input is a thousand times bigger. The logarithm went up by 10.
Multiplying the input adds to the logarithm. Every time n doubles, log n grows by just one. Every time n is multiplied by a thousand, it grows by about ten. That is why anything that takes "log n" steps barely notices when the data gets huge.
Why programmers care
An algorithm that halves the remaining work at each step takes log n steps. That pattern is everywhere.
Example
Finding a word in a dictionary
Open it in the middle. Is your word before or after this page? Throw away the half it cannot be in. Open the remaining half in the middle. Repeat.
A dictionary of a million words needs at most about 20 looks. That is binary search.
Reading from the first page would need up to a million.
| Where | What is halved or multiplied | Steps |
|---|---|---|
| Binary search | The range still to search | log n |
| A balanced search tree | Each level splits the items in two | log n levels deep |
| A database index | Each page splits the range in hundreds | A few levels for billions of rows |
| Merge sort | The list is split in half, log n times | n × log n in total |
| A heap | The tree is log n levels deep | log n per insert |
When you see O(log n) in a description of an algorithm, read it as: "doubling the data adds one step". See Reading Big-O from Code.
What about other bases?
A logarithm can use any number in place of 2.
- Base 10 asks how many times you divide by ten to reach 1. log₁₀ of 1,000 is 3. It is roughly the number of digits, minus one.
- Base 100 would describe a database index where each page has 100 entries: a million rows is 3 levels.
For reasoning about speed, the base hardly matters. Changing base only multiplies the answer by a fixed number. log₂ of n is always about 3.3 times log₁₀ of n. That is why Big-O just says "log n" without naming a base.
Logarithmic scales
Logarithms also appear when a quantity covers an enormous range. On a normal scale the small values would be invisible next to the large ones. So the scale counts multiplications instead.
- Earthquake magnitude: one step up is ten times the ground motion.
- Decibels: ten more is ten times the sound power.
- Charts with a log axis: each gridline is ten times the last, so steady percentage growth shows as a straight line.
In each case, equal steps on the scale mean equal ratios, not equal amounts.
Two handy rules of thumb
- 2 to the power 10 is about a thousand. So log₂ of a thousand is about 10, a million about 20, a billion about 30.
- The number of bits needed to store n different values is log₂ n, rounded up. A million ids need 20 bits.
Key takeaways
- The base-2 logarithm of a number is how many times you can halve it before reaching 1.
- It is the reverse of a power: 2 to the power 20 is about a million, so log₂ of a million is about 20.
- Logarithms grow very slowly: doubling n adds only one.
- Any algorithm that halves the problem at each step takes about log n steps.
- The base only changes the answer by a fixed factor, so Big-O just says log n.