Exponents, logs & growth

The idea

Exponentials grow by repeated multiplication; logarithms ask how many multiplications it took to reach a given number. In computer science, logarithms show up whenever a problem is repeatedly halved, and exponentials show up in brute-force search spaces — comparing growth rates like these is central to algorithm analysis.

Real-world: finding a name in a sorted directory

Binary search checks the middle entry and discards half of the remaining names at each step, so a directory of 1,024 names shrinks to 512, then 256, then 128, and so on. Reducing 1,024 possibilities down to one takes 10 halvings, because $1024 = 2^{10}$ — this is why binary search runs in about $\log_2(n)$ steps.

Worked example

1. Binary search halves the remaining range each step
2. $1024 = 2^{10}$
3. Ten halvings reduce 1,024 candidates to one; an ordinary successful search may perform an additional final comparison
4. So the search takes about $\log_2(n)$ steps—up to 11 comparisons for 1,024 items, depending on the convention and implementation

Cheat sheet

$2^x = n \iff \log_2(n) = x$

• $2^x = n$ and $\log_2(n) = x$ say the same thing from two directions.
• Doubling the input size adds exactly one more step to a $\log_2(n)$ algorithm, like binary search.
• $2^n$ eventually outgrows every polynomial, no matter how large that polynomial's degree is.
• Counting halvings (or doublings) is the same operation as taking a base-2 logarithm.