Logarithms & Exponents
The problem
Costs and capacities in real systems often grow or shrink multiplicatively — doubling traffic, halving a search space. Logarithms and exponents are the vocabulary for multiplicative change, and without them 'why is binary search fast' can only be observed, never explained.
Why now
Functions and relations gives the general notion of a mapping, but exponential growth and its inverse have a specific relationship — 'how many times do I multiply to reach this value?' — that needs its own vocabulary before it can be used to reason about algorithms.
Mental model
Exponentiation is repeated multiplication; a logarithm answers 'how many times do I halve or double to get from 1 to this number?' Every time an algorithm throws away half the remaining problem — binary search, balanced trees, binary-chop debugging — it is taking a logarithm of the problem size, and log tells you how many throw-aways remain.
Requires
- Functions & RelationsMathematical Thinking
Logarithm and exponential are defined as inverse functions of each other; without the function/inverse vocabulary, that relationship can't be stated precisely.
Unlocks
Used in
- Binary search and balanced-tree depth (O(log n))
- Information theory — bits needed to represent N states is log₂N
- Exponential backoff in retry logic and rate limiting
- Compound growth in capacity planning (traffic doubling every few months)
Projects
- Trace binary search on a 1000-element array by hand and count comparisons; compare to log₂(1000)
- Model exponential backoff (base delay, multiplier, cap) for a retrying HTTP client and graph the delay sequence
Examples
- A balanced binary tree with 1,000,000 nodes has depth ~20, because log₂(1,000,000) ≈ 20
- Doubling server capacity every time load doubles keeps cost-per-request roughly constant
Resources
- Logarithms — Khan Academyarticle
- Growth rates — MIT 6.042Jcourse
Mastery checklist
- I can compute log₂ of a power of two without a calculator and explain what it means
- I can explain why binary search is O(log n) in terms of halving
- I can compute how many bits are needed to represent N distinct states
- I can design an exponential-backoff schedule and explain why it beats fixed-interval retry