Exponential growth and trade-offs

Step 1 Warm-up recall

From M5.L3: which is cheaper at n = 20, 100n or n×n?

Your answer

Private: nothing you type here is sent or stored.

Step 2 Learning goal

By the end of this lesson you can:

• describe exponential growth (Foundation);
• compute 2 to the power n for small n (Core);
• explain a time-versus-memory trade-off (Core).

Step 3 A familiar example

Each new switch added to a panel doubles the number of on and off settings. Ten switches give a thousand settings; thirty give over a billion.

Step 4 Clear explanation

In exponential growth the cost doubles each time n increases by one, so the cost is 2 to the power n. A method that checks every subset of a list of n items must examine 2 to the power n subsets.

Adding one item doubles the work. Thirty items already mean more than a billion checks, so a method of this kind is practical only for small n, and a cleverer method is needed, or an answer that is good rather than perfect. Some problems are not known to have a fast method at all, a topic that returns in Module 8.

Cost is not only time. A method can be faster if it keeps extra data in memory: for example, storing a sorted copy of a list speeds later searches but uses more memory. This is a trade-off. Simplicity is another: a plain method that is easy to check may be the better choice for small inputs. Computers offer both fast and large memory, and designers trade one against the other; see the entry on the computer.

Step 5 Worked example (4 marks)

How many subsets must be checked for 12 items?

1. Use 2 to the power n with n = 12. (1 mark)
2. 2 to the power 10 is 1,024. (1 mark)
3. Two more doublings give 1,024 × 4 = 4,096. (1 mark)
4. Answer: 4,096 subsets. (1 mark)

Step 6 Learner practice (instant-marked)

Step 7 Recap

• Exponential growth doubles the cost per extra item.
• 2 to the power 30 is over a billion.
• Time, memory and simplicity trade against each other.

Step 8 Exit ticket (ungraded)

Give the number of subsets for 5, 10 and 15 items.

Your answer

Private: nothing you type here is sent or stored.

Step 9 Go further (Extension)

Describe one trade-off between memory and time in an everyday tool.