Growth rates: constant, logarithmic, linear, quadratic

Step 1 Warm-up recall

From M5.L1: how many pairs among 4 items?

Your answer

Private: nothing you type here is sent or stored.

Step 2 Learning goal

By the end of this lesson you can:

• name four growth rates (Foundation);
• match a method to its growth (Core);
• predict the effect of doubling n (Core).

Step 3 A familiar example

Reading the first item of a list costs the same however long the list is. Reading every item costs more as the list grows. Comparing every pair costs far more.

Step 4 Clear explanation

The growth rate of a method describes how its cost changes as n increases. Four patterns cover most methods you have met.

The table shows why growth matters more than small differences: at n = 1,000, binary search takes about 10 steps, linear search 1,000 and a pairwise comparison a million. To predict the effect of doubling, use the pattern in the figure.

Doubling the input doubles a linear cost but quadruples a quadratic cost, so a method that seems acceptable at 100 items can become very slow at 10,000. Organising the data differently, for example sorting it first, can change which growth rate applies, as binary search showed. See also the entry on the computer.

Step 5 Worked example (4 marks)

A pairwise comparison takes 10,000 comparisons at n = 100. Estimate the cost at n = 200.

1. The growth is quadratic. (1 mark)
2. Doubling n quadruples the cost. (1 mark)
3. 10,000 × 4 = 40,000. (1 mark)
4. Answer: about 40,000 comparisons. (1 mark)

Step 6 Learner practice (instant-marked)

Step 7 Recap

• Constant, logarithmic, linear and quadratic are the common rates.
• Doubling n doubles linear and quadruples quadratic cost.
• Growth outweighs small differences in speed.

Step 8 Exit ticket (ungraded)

Name the growth of linear search, binary search and a pairwise comparison.

Your answer

Private: nothing you type here is sent or stored.

Step 9 Go further (Extension)

Estimate the pairwise cost for n = 400 given 10,000 at n = 100.