---
format: 1
concept: "logarithms"
kind: "explanation"
title: "How many times you halve"
labels: {"lang":"en","level":"beginner"}
changes: []
by: "si"
declaration: {"company":"anthropic","model":"claude-opus","version":"5.5","thinking":"high","app":"claude-code","tools":[],"sources":["https://en.wikipedia.org/wiki/Logarithm","https://en.wikipedia.org/wiki/Binary_logarithm"]}
---
A **logarithm** answers one question: *how many times do I multiply by this number to get to that one?*

$2 \times 2 \times 2 = 8$, three 2s. So the logarithm of 8 in base 2 is 3, written $\log_2 8 = 3$.

| $n$ | 1 | 2 | 4 | 8 | 16 | 1,024 | 1,048,576 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $\log_2 n$ | 0 | 1 | 2 | 3 | 4 | 10 | 20 |

## The same thing backwards: halving

Read the table the other way. $\log_2 n$ is also how many times you can **halve** $n$ before you reach 1: 16 → 8 → 4 → 2 → 1 is four halvings, and $\log_2 16 = 4$.

That's why logarithms turn up in computing. Any method that throws away half of what's left at each step, like binary search, needs about $\log_2 n$ steps for $n$ items.

## It grows very slowly

Doubling $n$ adds just **1** to $\log_2 n$. A thousand items is about 10 halvings; a million is about 20; a billion is about 30. The number of items grew a million-fold and the steps only went from 10 to 30.

## Numbers that aren't powers of 2

$\log_2 1000$ isn't a whole number: it's about 9.97, because $2^{10} = 1024$ is just over 1,000. When counting steps, round **up**: 1,000 items take at most 10 halvings.

## Other bases

The base is what you multiply by. $\log_{10} 1000 = 3$ because $10 \times 10 \times 10 = 1000$: it counts digits, roughly. In computing, base 2 is the usual one, and $\log n$ with no base often means $\log_2 n$.