A Refresher on Logarithms

If you are taking Data Structures with me, logarithms are about to show up everywhere: binary search, balanced trees, the cost of sorting. You met them in a math class once, and then you probably never used them again. This page is a refresher — no prior fluency assumed. Let's rebuild logarithms from the one idea they rest on.

What a logarithm actually is

A logarithm is the inverse of exponentiation. That single sentence is the whole game.

Exponentiation asks: start with a base, raise it to a power — what do you get? A logarithm runs that backwards: you know the base and the result; what was the power?

We write it like this:

$${\log }_{b}x=y\text{means}{b}^y=x.$$

Read ${\log }_{b}x$ as "the power you raise $b$ to in order to get $x$." The $b$ is the base.

Let's pin this down with one concrete case we'll come back to throughout this page. Take base $2$ and $x=8$:

$${\log }_{2}8=3\text{because}{2}^3=8.$$

That's it. ${\log }_{2}8$ is just the answer to "two to the what gives eight?" — and the answer is three. Whenever a logarithm looks intimidating, translate it back into that question.

(Two small print conditions, so nothing surprises you later: the base $b$ must be positive and not equal to $1$, and you can only take the log of a positive $x$. You can't raise a positive base to any power and land on zero or a negative number, so those inputs have no answer.)

Two values fall straight out of the definition:

$${\log }_{b}1=0\text{because}{b}^0=1,$$

$${\log }_{b}b=1\text{because}{b}^1=b.$$

Anything to the zero power is one, so the log of one is always zero. And the base raised to the first power is itself, so the log of the base is always one.

The laws of logarithms

There are three laws you'll lean on, plus a fourth for switching bases. Here they are together; we'll derive each one in the next section.

$$\begin{array}{rlrl}{\log }_b(xy)& ={\log }_{b}x+{\log }_{b}y& & \text{(product)}\\ {\log }_b\left(\frac{x}{y}\right)& ={\log }_{b}x-{\log }_{b}y& & \text{(quotient)}\\ {\log }_b(x^k)& =k{\log }_{b}x& & \text{(power)}\\ {\log }_{b}x& =\frac{{\log }_{c}x}{{\log }_{c}b}& & \text{(change of base)}\end{array}$$

These laws use the same conditions as before: the bases are positive and not equal to $1$, and every quantity inside a logarithm must be positive.

Notice the shape of the first three: multiplication on the inside turns into addition on the outside, division turns into subtraction, and a power turns into multiplication. A logarithm often knocks an operation down one level. That is exactly what made logarithms useful for hand calculation centuries ago, and it is why they tame the multiply-heavy counting we do when we analyze algorithms.

Before deriving anything, let's just check the product law on numbers we can verify by hand:

$${\log }_2(4\cdot 8)={\log }_{2}32=5,{\log }_{2}4+{\log }_{2}8=2+3=5.✓$$

Same answer both ways. Good. Now let's see why.

Where the laws come from

Every law here is an exponent law wearing a disguise. The trick is the same each time: name the logs we're working with, rewrite everything as powers of $b$, and use the exponent rule we already know.

The product law

We want to understand ${\log }_b(xy)$. Start by naming the two logs on the right:

$$m={\log }_{b}x,n={\log }_{b}y.$$

By the definition of a logarithm, that's the same as saying:

$$b^m=x,b^n=y.$$

Now multiply $x$ and $y$ by multiplying their power-of-$b$ forms:

$$\begin{array}{rl}xy& =b^m\cdot b^n\\ & =b^{m+n}.\end{array}$$

The second line is the one exponent law we need: multiplying same-base powers adds the exponents. Now read that result back through the definition of a logarithm — $xy$ equals $b$ raised to $m+n$, so the log of $xy$ is $m+n$:

$${\log }_b(xy)=m+n={\log }_{b}x+{\log }_{b}y.$$

That's the product law. Multiplication inside became addition outside, because multiplying powers adds their exponents.

The quotient law

Same setup, division instead of multiplication. With $b^m=x$ and $b^n=y$:

$$\begin{array}{rl}\frac{x}{y}& =\frac{b^m}{b^n}\\ & =b^{m-n}.\end{array}$$

Dividing same-base powers subtracts the exponents. Reading it back:

$${\log }_b\left(\frac{x}{y}\right)=m-n={\log }_{b}x-{\log }_{b}y.$$

The power law

Now ${\log }_b(x^k)$. Name the inner log, $m={\log }_{b}x$, so $b^m=x$. Then:

$$\begin{array}{rl}{x}^k& =(b^m{)}^k\\ & =b^{mk}.\end{array}$$

Raising a power to a power multiplies the exponents. So $x^k$ is $b$ raised to $mk$, which means:

$${\log }_b(x^k)=mk=k{\log }_{b}x.$$

A power inside comes out front as a plain multiplier. This is the law that lets us pull an exponent down — we'll use it in a moment to switch bases.

Change of base

Calculators and the laws above are happy in any base, but the log on your calculator is usually base $10$ or base $e$, while in algorithms we almost always want base $2$. So we need a way to compute ${\log }_{b}x$ using some other base $c$ we can evaluate.

Let $y={\log }_{b}x$, which means $b^y=x$. Both sides are equal, so their logs in base $c$ are equal too:

$$\begin{array}{rl}{\log }_c(b^y)& ={\log }_{c}x\\ y{\log }_{c}b& ={\log }_{c}x.\end{array}$$

The second line is just the power law applied to the left side — it pulled the exponent $y$ out front. Now solve for $y$ by dividing:

$$y=\frac{{\log }_{c}x}{{\log }_{c}b}.$$

And $y$ was ${\log }_{b}x$ all along, so:

$${\log }_{b}x=\frac{{\log }_{c}x}{{\log }_{c}b}.$$

Let's confirm it on our running example, getting ${\log }_{2}8$ out of base-$10$ logs:

$${\log }_{2}8=\frac{{\log }_{10}8}{{\log }_{10}2}\approx \frac{0.903}{0.301}=3.✓$$

There's a quiet payoff hiding here. Changing the base only ever divides by a constant (${\log }_{c}b$ doesn't depend on $x$). So ${\log }_{2}n$, ${\log }_{10}n$, and $\ln n$ differ only by a constant factor. When we care about how a cost grows rather than its exact value, the base of the logarithm stops mattering — which is why you'll often see people write just "$\log n$" and not fuss over the base.

Where this shows up in algorithm analysis

Two quick examples, both built on the same observation: doubling and halving are the operations logarithms count.

Binary search: counting halvings

Binary search looks for a value in a sorted array by checking the middle, then throwing away the half that can't contain the target. Each comparison either finds the target or cuts the remaining range roughly in half. Start with $n$ candidates:

$$n\to \frac{n}{2}\to \frac{n}{4}\to \cdots \to 1.$$

After $x$ halvings the range has size about $n/2^x$. Ignoring the small off-by-one details for the moment, the search is down to a single candidate when:

$$\begin{array}{rl}\frac{n}{2^x}& =1\\ 2^x& =n\\ x& ={\log }_{2}n.\end{array}$$

The middle line just multiplies both sides by $2^x$; the last line reads $2^x=n$ through the definition of a logarithm — $x$ is the power of $2$ that gives $n$. So binary search takes on the order of ${\log }_{2}n$ comparisons. The exact worst-case count has a small rounding/off-by-one term, but the growth is logarithmic.

Check it against our running case. With $n=8$: $8\to 4\to 2\to 1$ is three halvings, and ${\log }_{2}8=3$. Depending on exactly when the target is found, binary search may use one more comparison than the number of halvings, but the logarithm is the part that controls the growth. That's the whole reason a sorted array is worth the trouble — searching a million elements costs about ${\log }_{2}1,000,000\approx 20$ comparisons, not a million.

Counting bits: the inverse direction

Here's the same idea running the other way. For a positive integer $n$, how many binary digits — bits — do you need to write the number $n$?

Each bit you add doubles how many values you can represent. With $d$ bits you can write $2^d$ different numbers, namely $0$ through $2^d-1$. So to have a code for every value from $0$ through $n$, you need enough bits that $2^d\ge n+1$. Solving the rough version, $2^d\approx n$, for $d$ gives $d\approx {\log }_{2}n$ — the same log, because doubling-per-bit is just halving-per-step read backwards.

Pinned to a number: $8$ in binary is $1000$, which is $4$ bits. The exact count is $\lfloor {\log }_{2}n\rfloor +1$ for $n\ge 1$, so for $8$ we get $\lfloor {\log }_{2}8\rfloor +1=3+1=4$. (The floor and the $+1$ are bookkeeping for the off-by-one; the ${\log }_{2}n$ is the part that matters.)

The take-home message

A logarithm answers one question: what power gives this number? Every law is an exponent law read through that lens — products become sums, powers become multipliers, and changing the base only ever costs a constant factor. In this course, ${\log }_{2}n$ captures the number of times you can halve $n$ before reaching $1$ (exactly when $n$ is a power of $2$, and up to rounding otherwise). Keep that picture in mind and the cost of binary search, balanced trees, and good sorting algorithms will all read the same way.