Pointer Walk

Logarithms

How many times can you halve a million before you reach one? Twenty. That question is all a logarithm is, and it is why log n algorithms are fast.

Maths for ProgrammersBeginner7 min read

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.

Halving 1,000,000Interactive
Start at
1,000,000

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.

nlog₂ n
164
1,02410
1,000,000about 20
1,000,000,000about 30
1,000,000,000,000about 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.

WhereWhat is halved or multipliedSteps
Binary searchThe range still to searchlog n
A balanced search treeEach level splits the items in twolog n levels deep
A database indexEach page splits the range in hundredsA few levels for billions of rows
Merge sortThe list is split in half, log n timesn × log n in total
A heapThe tree is log n levels deeplog 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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    6 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress