Maths/Big O notation

Logarithms, and why the base stops mattering

After thiswhat you will be able to doCount how many repeated divisions reduce a range to one item, convert that count between logarithm bases, and explain why Big O discards the resulting fixed multiplier.

Questionwhat this lesson answersIf repeatedly halving a range until one item is left is the whole of what a logarithm counts, why does it make almost no difference whether you halve the range, cut it in three, or cut it in ten?

Not coveredwhat this lesson leaves outWe stay with the logarithm as the number of times you can divide a range before it is gone. The natural logarithm, the number e, and the logarithm as the inverse of a smooth doubling are all left alone.

Imagine looking for one value in a range already arranged from smaller to larger. Such a range is called sorted. Look at the middle value. If the target is smaller, everything after the middle is wrong; if it is larger, everything before the middle is wrong. Throw the wrong half away and look at the middle of what remains. One look at a middle value is the unit we will count, called a probe. The question is plain: how many times can a range of ${n}$ items be halved before only one item is left?

Start with 1,000 items and keep the remaining whole number of items at each cut. The range goes from 1,000 to 500, 250, 125, 63, 32, 16, 8, 4, 2, and 1. That is 10 halvings. The small rounding up at 125 divided by two does not change the count. The nearby exact landmark is ${2^{10} = 1024}$, where the raised 10 says to multiply 2 by itself ten times. A million items need about 20 halvings because ${2^{20} = 1048576}$, only a little larger than one million. A range can grow from one thousand to one million items, a thousandfold increase, while the number of probes only moves from about 10 to about 20.

Only now do the names earn their place. Count how many 2s must be multiplied together to reach a size, and you have the count of these halvings. That count is called the base-2 logarithm of the size, written ${\log_2 n}$. The repeated multiplier, here 2, is called the base. The phrase “about 10” means a search over whole items must make whole probes. That is an integer search: it uses enough halvings to bring the range down to one, even when ${n}$ is not itself an exact product of 2s.

This count has a signature that makes its growth feel flat. Double the range and exactly one more halving is needed. One more halving undoes one doubling. A range of ${64}$ takes six probes when each cut has two pieces, while a range of ${128}$ takes seven. A two-piece search is also called a binary search. The same statement holds at every size in this integer model, not just at powers of two. That is why this growth is so slow: a large multiplication of the input becomes one addition to the probe count. The Doubling test door takes that signature and asks how to recognise a growth when nobody has named it for you.

What changes if each probe cuts the range into three pieces instead? The procedure is the same, but the repeated multiplier is now 3. Count how many 3s must be multiplied together to reach the size, and the result is the base-3 logarithm. The rule that translates between repeated multipliers is called change of base:

The number ${\log_2 3}$ is about 1.585. So, before the final whole-probe rounding, cutting in three takes ${\dfrac{1}{1.585} \approx 0.63}$ times as many steps as halving. Cutting in ten gives ${\dfrac{1}{\log_2 10} \approx \dfrac{1}{3.32} \approx 0.30}$ times as many. The number comparing these counts is a ratio: the base-3 count divided by the base-2 count is about 0.63, and the base-10 count divided by the base-2 count is about 0.30.

Those are real, permanent differences in the count. With a large range, cutting in three really does save about 37 percent of the probes compared with halving. Cutting in ten saves about 70 percent. A particular search still has to round its count to whole probes, so a small range can land one probe above or below the decimal comparison. That rounding does not change the same fixed number multiplying every count, called a fixed multiplier. The multiplier depends on the chosen base, not on the size of the range.

This is the honest turn: the base absolutely changes how many probes you do. Saying that the base does not matter is not a fact about logarithms. It becomes true only after a choice from the previous lesson. That choice discards a fixed multiplier, a number that multiplies every count by the same amount. Changing from base 2 to base 3 multiplies the count by about 0.63. Changing from base 2 to base 10 multiplies it by about 0.30. Neither difference fades away as the range grows. They are being set aside on purpose.

This is why people write ${O(\log n)}$ with no base. The notation ${O(\ldots)}$ keeps a growth shape after fixed multipliers have been discarded. Every base greater than one differs from every other base by one such multiplier, so the missing base carries a meaning. It says that the comparison has chosen not to distinguish 10 probes from roughly 6.3 probes, or 20 from roughly 6, when they arise from the same range size. It is not sloppy notation. It is a record of what the comparison agreed to stop seeing.

The same choice explains a second contrast. A logarithm adds one when its input doubles. A linear term adds an amount as large as the input when its input doubles. For large enough inputs, the first grows more slowly than any straight line, no matter which base was chosen. That statement needs a way to establish eventual behaviour rather than merely looking at examples. The Limits and dominance door is where that proof begins.