Maths/Big O notation

The doubling test

After thiswhat you will be able to doUse T(2n)/T(n) to diagnose a likely growth shape, and recognise when lower-order terms make the diagnosis premature.

Questionwhat this lesson answersEach growth shape answers a doubled input in its own way: constant stays, linear doubles, quadratic quadruples. Run that backwards, measuring how the cost responds when you double the input and reading off the shape you were not told, and you have a diagnostic. How does it work and where does it mislead?

Not coveredwhat this lesson leaves outWe read a growth shape off the ratio of costs at n and 2n for the shapes this arc has met. We do not handle noisy real measurements, and we do not prove that a measured ratio pins the shape.

The cost lesson gave each piece of work a response to a doubled input. Work done once stayed put. Work done once for each input item doubled. Work that paired each item with every item became four times as large because both directions doubled. Those responses can be used in reverse. If the shape of a cost is hidden, measure it at one input size and then at twice that size. The way the two measurements compare is evidence about the arrangement of the work.

Start with the comparison before its name. Let ${T(n)}$ be the cost at an input of ${n}$ items. Make the input ${2n}$ items and divide the second cost by the first. The resulting number says how many copies of the first cost fit into the second. That number is called the doubling ratio:

The response has a clean signature when one shape is the whole cost. A cost that stays fixed gives one. A cost that keeps pace with its input gives two. A cost made by multiplying the input by itself gives four. If the input is multiplied by itself three times, there are three independent input-sized choices. That shape is called cubic, and its response is eight. One more arrangement doubles the cost itself each time a single item is added, so doubling the input multiplies the cost many times over and its ratio grows rather than settling. That shape is called exponential.

Here are the signatures the arc has met. The input-times-halving-count row is the shape often described as one logarithmic count for each input item. It has a ratio a little above two because doubling both doubles the input part and adds one to the halving count.

The entries are arithmetic, not labels to memorise. For a cost built by multiplying ${n}$ by itself a fixed number of times, doubling every copy multiplies the cost by two raised to that same number. Squaring gives four and cubing gives eight. For the input-times-halving-count shape, the extra halving is why the ratio is just above two, then slowly approaches it. For a logarithmic cost, the ratio is a less useful clue because both values are close together. Its difference is the clearer clue: doubling adds exactly one halving. For the exponential cost where ${T(n) = 2^n}$, the calculation is

The ratio itself grows with ${n}$, which separates this shape from every fixed multiplier in the table.

The method is now short. Measure the cost at ${n}$ and at ${2n}$. Form their quotient. A value near four suggests the input was paired with itself. A value near two suggests one pass through the input. A value near one could mean fixed work or a logarithm, so check the difference too. If the difference stays one while the ratio drifts toward one, repeated halving is the better guess. If the ratio itself keeps climbing, an exponential response is the warning sign.

That word “suggests” matters. The ratio is clean only after one piece of a cost has become the visible part of the total. Return to the running polynomial from the arc. It has the long-run shape of the input multiplied by itself, but at a small input the fixed setup and one-pass work are still present:

The ratio is well below four, not because the eventual shape changed, but because the other pieces have not yet become small beside the piece that grows like the input times itself. Those slower pieces are called lower-order terms. They contaminate a small measurement by mixing their own doubling responses into the quotient. The cost’s long-run shape has not failed. The measurement is asking too early.

As the input grows, the ratio climbs toward the clean quadratic response:

The approach is what the n zero threshold from the What O(f) actually is door was built to name. Before that threshold, the larger piece has no promise to dominate. The When the constants come back door gave the same finite-size fact a practical form: the pieces we later discard can decide what a program looks like at the sizes it actually runs.

The doubling test is therefore a way to form a quick guess from two measurements, not a proof. It works best after the input is large enough for one response to dominate. A clean ratio can point you toward the right count. It cannot replace doing that count, and a dirty ratio may only mean that the input has not reached the part of the curve where the intended shape shows itself.