Rising by less each time
A student practices a task and is scored after 1, 2, 4, 6 and 9 trials. The scores are 8, 10, 12, 13.5 and 14.5. They keep rising, but by less and less. Going from 1 trial to 2 adds 2 points. Going from 2 to 4 trials adds 2 points, which is 1 point a trial. Going from 4 to 6 adds 1.5 points, 0.75 a trial, and going from 6 to 9 adds 1 point, about 0.33 a trial.
A straight line cannot fit data like this, because a line adds the same amount for every trial. Nor can exponential growth, which adds more at each step, not less.
The five scores against the number of trials. The points rise steeply at first and then more and more gently.
A logarithmic model
A logarithmic model is y = a + b ln x, where a and b are fixed numbers and ln is the natural logarithm. It bends the same way as the data. By the product law, ln(2x) = ln 2 + ln x, so each time x doubles, ln x goes up by the same ln 2 = 0.693 and the model goes up by the same b ln 2. Doubling the number of trials from 1 to 2 costs one trial, and doubling it from 8 to 16 costs eight, for the same gain.
The scores fit that pattern: from 1 trial to 2 they rose by 2, and from 2 to 4, the next doubling, they rose by 2 again.
ln x has no largest value, so the model has no ceiling: it rises forever, but more and more slowly.
The gold curve is the model y = 8 + 3 ln x, through the five scores. It keeps rising across the whole graph, less steeply all the time.
Plot y against ln x
Write X for ln x. The model y = a + b ln x becomes y = a + bX, a straight line in X. So plot each score against ln x instead of x. The values of ln x for 1, 2, 4, 6 and 9 trials are 0, 0.693, 1.386, 1.792 and 2.197, to 3 decimal places.
Against ln x the five scores lie close to a straight line. Only the axis across has been changed: the scores themselves are plotted as they are.
The same five scores with ln x across. They lie close to the line y = 8 + 3 ln x, which meets the vertical axis at 8 and rises 3 for each 1 across.
Read a and b off the line
The line meets the vertical axis at 8, so a = 8. That is where ln x = 0, which is at x = 1 trial, so a is the model's score after 1 trial.
The line passes through (0, 8) and (2, 14), so its gradient is (14 − 8) ÷ (2 − 0) = 3, and b = 3: the score rises 3 for each 1 that ln x rises. The model is y = 8 + 3 ln x.
Unlike the exponential and the power law, nothing needs undoing here. The scores were plotted as they are, so the intercept is a itself and the gradient is b itself.
Fitting from two readings
Two readings are enough to fix a and b, even when neither is at x = 1. Take the scores after 2 trials and after 6: 10 and 13.5. Each gives an equation: a + b ln 2 = 10 and a + b ln 6 = 13.5.
Subtract the first from the second, and a disappears: b(ln 6 − ln 2) = 3.5. By the quotient law, ln 6 − ln 2 = ln 3 = 1.0986, so , to 2 decimal places. Then a = 10 − 3.19 × ln 2 = 10 − 3.19 × 0.693 = 7.79, to 2 decimal places.
This is the gradient of the line through two points on the ln x plot: a rise of 3.5 over a run of ln 3. The model y = 7.79 + 3.19 ln x is close to y = 8 + 3 ln x, fitted to all five scores. Two readings far apart give a steadier fit than two close together.
Predicting
Put a value of x into the model. After 20 trials: ln 20 = 2.996, so y = 8 + 3 × 2.996 = 16.99, a score of about 17. The 11 trials from 9 to 20 add only about 2.4 points.
The model can also be run backward. To find when the score first reaches 18, solve 8 + 3 ln x = 18: , and e to the power undoes ln, so . At 28 trials the model gives 17.997, just under 18, and at 29 trials it gives 18.10, so the score first reaches 18 after 29 trials.
Where the model breaks
Close to x = 0, ln x falls without limit, and so does the model. At x = 0.1 it gives 8 + 3 ln 0.1 = 1.09, and it gives 0 at . At x = 0 it gives nothing at all, since ln 0 does not exist. Here x counts trials, so the model is only used for x of at least 1.
Far out, the model has no ceiling, but a score usually does. If the task is marked out of 20, the model reaches 20 when ln x = 4, at , and after 55 trials it predicts more than full marks. A fitted model is trusted only over about the range of the data it was fitted to.
The model y = 8 + 3 ln x over 60 trials, with the line for full marks, 20. At the far left the curve drops to 0 just right of the vertical axis, at x = 0.07, and at about 55 trials it crosses the full-marks line.
Which axis takes the logs
Three models, three plots. For exponential growth, , take the logs of the y values: log y against x is straight, with gradient log b. For a power law, , take the logs of both: log y against log x is straight, with gradient n. For a logarithmic model, y = a + b ln x, take the logs of the x values only: y against ln x is straight, with gradient b.
Exponential growth adds more at each step, by a constant factor. A logarithmic model adds less at each step. Which axis makes the points straight is what picks the model.
For each model, what to plot across and up to get a straight line, and what its gradient is.
The usual mistakes
Treating the model as a straight line in x. Going from 1 trial to 2 added 2 points, but that does not mean 2 points a trial: at that rate 20 trials would give 8 + 2 × 19 = 46, far above the model's 17.
Undoing ln with a power of 10. If ln x = 3.333, then , not , which is over 2000.
Taking logs of the scores. For this model the scores stay as they are; it is x whose logarithm goes on the axis.
Swapping a and b. The line y = 3 ln x + 8, against ln x, gives the model y = 8 + 3 ln x: the number added on is a, and the number multiplying ln x is b.
Putting in x instead of ln x, or leaving out a. After 20 trials the prediction is 8 + 3 × ln 20 = 8 + 3 × 2.996 = 17.0, not 8 + 3 × 20 = 68, and not 3 × 2.996 = 9.0.
A logarithm against a line
The next problem compares a count of steps with steps. Dividing both by n compares with n. By the change of base rule, , so , to 1 decimal place: a logarithmic model with a = 0 and b = 46.2.
For small n, is far bigger: at n = 16 it is 32 × 4 = 128. But a logarithmic model gains less and less, while n rises at a steady 1 for every 1 across, so n catches up with and then stays ahead. The crossing is easiest to find at powers of 2, where is a whole number: at , 32 × 8 = 256.
The problem also needs , which is , to 2 decimal places.
Worked example: Two Sorting Programs and a Search Through Every Group on a Sensor Chip: Where One Program Overtakes the Other, and the Largest Job Each Finishes in a Second
Question A sensor chip carries out one million basic steps per second. To sort a list of n readings, program A takes 32nlog2 n steps and program B takes n2 steps. A third task, choosing the best group of readings by checking every possible group, takes 2n steps for n readings. (a) For which list lengths n ≥ 2 does B take fewer steps than A, and for which n do the two take the same number? (b) What is the largest n that B can sort, and the largest n for which the group search finishes, in no more than one second? What are these two numbers on a chip 64 times as fast?
1.B takes fewer steps than A when n2 < 32nlog2 n. Divide both sides by n: n < 32log2 n, which compares n with a multiple of its logarithm.
Dividing by n, B takes fewer steps than A when n < 32log2 n. 2.Try powers of 2, where log2 n is a whole number. At n = 128: 32 × 7 = 224, more than 128. At n = 256: 32 × 8 = 256, equal. At n = 512: 32 × 9 = 288, less than 512.
At powers of 2 the logarithm is a whole number: 32log2 n is 224, 256 and 288 at n = 128, 256 and 512. 3.(a) The ratio nlog2 n is 2 at n = 2 and rises for every n ≥ 3, so it reaches 32 only once, at n = 256. B takes fewer steps for 2 ≤ n < 256, the two take the same number, 65536, at n = 256, and A takes fewer from then on.
(a) The curves meet once, at n = 256, with 65536 steps each. B takes fewer steps below 256 and A above it. 4.One second is 1000000 steps. For B, n2 ≤ 1000000 gives n ≤ 1000. For the group search, 2n ≤ 1000000 gives n ≤ log2 1000000 ≈ 19.9, so n ≤ 19: 219 = 524288 and 220 = 1048576.
In one second of a million steps B sorts up to 1000 readings, and the group search handles up to 19. 5.A chip 64 times as fast carries out 64000000 steps in a second. For B, n2 ≤ 64000000 gives n ≤ 8000. For the group search, 64 = 26 adds 6 to the logarithm: n ≤ 19.9 + 6 = 25.9, so n ≤ 25, since 225 = 33554432 and 226 = 67108864.
On a chip 64 times as fast, B sorts 8 times as many readings, but 64 = 26 adds only 6 to the group search. 6.(b) In one second B sorts up to 1000 readings and the group search handles up to 19. On the faster chip these become 8000 and 25: eight times as many readings for B, but only 6 more for the group search.
(b) In one second: 1000 and 19. On the faster chip: 8000 and 25.
Answer: (a) B takes fewer steps for 2 ≤ n < 256, the same number at n = 256, and more for n > 256; (b) B sorts up to 1000 readings and the group search handles up to 19; on the faster chip, 8000 and 25
Common mistakes
- Concluding from small lists that B is always faster: at n = 16, B takes 256 steps and A takes 32 × 16 × 4 = 2048. The logarithm grows more slowly than n, so 32log2 n falls behind n in the end.
- Multiplying the group search's 19 by 64, or by 8 as for B. Each extra reading doubles its steps, so a chip 64 = 26 times as fast buys only 6 more readings.