Logarithmic Time — The Power of Halving

Look up a word in a paper dictionary and you never read page by page. You open near the middle, see you have gone too far, and throw away half the book. A few halvings later you are on the right page. A dictionary of 1000 pages needs about 10 such halvings; one of 2000 pages needs about 11. That gentle growth is logarithmic time.

The rule

Halve the problem each step; doubling the input adds just one step.

If every step throws away half of what is left, the number of steps is the number of times you can halve n before reaching 1. That number is the base-2 logarithm of n, written log₂ n, and the growth rate is written O(log n).

The powers of two make it easy to feel:

Going from a thousand to a billion items multiplies n by a million, yet the steps only go from 10 to 30. Binary search on a sorted list is the classic example: compare with the middle item, keep the half that could still hold the target, repeat.

Halving needs a reason to throw half away. Binary search only works because the list is sorted; on an unsorted list, the middle item tells you nothing about where the target is.

The shortcut

Count in powers of two: 2¹⁰ ≈ one thousand, 2²⁰ ≈ one million, 2³⁰ ≈ one billion. To estimate log₂ n, find the nearest power of two and read off its exponent.

The trap: expecting a halving algorithm to handle twice the data in twice the time. It needs one extra step, not double.

Drills

Answer fast — trust the rule.

Remember

• Halve the problem each step: the step count is about log₂ n.
• 2¹⁰ ≈ thousand, 2²⁰ ≈ million, 2³⁰ ≈ billion.
• The trap: doubling the input adds one step, not double the steps — and halving needs sorted data.