A map-tile pyramid halves image width per level — why is the level count O(log n), not O(n)?

## The loop shape A zoom pyramid stores a map image at successively coarser resolutions: the base level at full detail, then a level at half the width, then a quarter, and so on until the whole world fits in a single small tile. The build loop looks like: ``` width = n levels = 0 while width > 1 build_level(width) width = width / 2 levels = levels + 1 ``` The question is how many times that loop body runs. ## Divide versus decrement This is the whole distinction, and it is the one candidates most often blur. - **Decrement:** `width = width - 1` (or `- 100`) reaches 1 after about n steps (or n/100). Subtracting a constant leaves the trip count **linear**: O(n). Dividing the constant out changes the coefficient, never the class. - **Divide:** `width = width / 2` reaches 1 after k steps where `n / 2^k = 1`, that is `2^k = n`, that is `k = log2(n)`. Repeated division gives a **logarithmic** trip count. The intuition worth carrying is that the logarithm is the inverse of exponential growth: asking "how many halvings take n down to 1" is the same as asking "how many doublings take 1 up to n". Doubling reaches large numbers fast, so the answer is small. For n = 4096 it is 12. For n = 1,000,000 it is about 20. For the number of atoms in a rock it is a couple of hundred. Logarithmic loops essentially never run many times, which is why an O(log n) step is treated as nearly free. ## Why the base does not matter Suppose the pyramid quartered the width per level instead of halving it. Then the level count is `log4(n)`. By the change-of-base identity, `log4(n) = log2(n) / log2(4) = log2(n) / 2` — exactly half as many levels. Half is a constant factor, and big-O drops constant factors, so both are O(log n). This is why the notation is normally written without a base at all. It is a real difference in practice (twelve levels versus six) and no difference in class. The misconception to name explicitly: `O(log4 n)` is not a smaller complexity class than `O(log2 n)`. Any two logarithms differ by a constant multiplier. Contrast this with `O(n)` versus `O(n^2)`, where no constant can bridge the gap. ## The follow-on trap: level count is not total work A logarithmic *number of levels* does not by itself make the build logarithmic, because each level does a different amount of work. If the base image is n by n pixels, each level has a quarter of the pixels of the level below it: `n^2, n^2/4, n^2/16, ...`. The total is a geometric series with ratio 1/4, which sums to `n^2 * 4/3`. So building the whole pyramid costs about one and a third times the base image — **linear in the number of source pixels**, not `pixels * log`. This is the general lesson about halving loops. When the per-iteration work is constant, `log n` iterations means O(log n) total. When the per-iteration work *shrinks geometrically*, the sum is dominated by the first term and the total is proportional to that first term. When the per-iteration work is *constant and large* — say each level re-reads the full source image — then `log n` iterations really do multiply, and the total becomes `n^2 log n`. Always multiply the trip count by the work per trip; do not read the loop's trip count as if it were the answer. ## Recognising the pattern elsewhere The same counting argument covers any loop whose control variable is multiplied or divided by a constant factor each pass: stepping through the levels of a balanced tree, walking the doubling capacities of a growing buffer, or ranging over powers of two. In each case the number of steps is logarithmic in the ratio between the start and stop values, and the base only shifts the constant. Conversely, a loop that adds or subtracts a fixed amount — no matter how large — is linear, and a loop that decrements by one from a bound that itself depends on an outer index gives the triangular sum instead.