Comparing methods and the crossover

Step 1 Warm-up recall

From M5.L2: doubling n for a quadratic method?

Your answer

Private: nothing you type here is sent or stored.

Step 2 Learning goal

By the end of this lesson you can:

• compute the cost of two methods at the same n (Foundation);
• find a crossover point (Core);
• choose a method for a stated workload (Core).

Step 3 A familiar example

A method with a heavy set-up but slow growth loses on tiny inputs and wins on large ones. Growth rate decides which in the end, but your actual input size decides which today.

Step 4 Clear explanation

Two methods can be compared by computing their step counts at the same input size. Take two invented methods: method A costs 100 × n steps (linear, with a large constant), and method B costs n × n steps (quadratic, with none).

For small n, B is cheaper; they are equal at n = 100; beyond that, A is cheaper, and the gap widens. The point where the lines cross is the crossover. To decide, find your expected n. If a task will only ever handle 50 items, B is better today. If it may grow to thousands, choose A. Growth rate wins in the long run, but input size decides in practice. A programmer working in any programming language faces the same choice between a simple method and a scalable one.

Step 5 Worked example (4 marks)

For methods A (100 × n) and B (n × n), which is cheaper at n = 500 and by how much?

1. A: 100 × 500 = 50,000. (1 mark)
2. B: 500 × 500 = 250,000. (1 mark)
3. A is cheaper. (1 mark)
4. Answer: A, by 200,000 steps. (1 mark)

Step 6 Learner practice (instant-marked)

Step 7 Recap

• Compute both costs at your expected n.
• The crossover is where the methods cost the same.
• Growth wins in the long run; input size decides today.

Step 8 Exit ticket (ungraded)

Find the cost of A and B at n = 20 and say which is cheaper.

Your answer

Private: nothing you type here is sent or stored.

Step 9 Go further (Extension)

Describe a task whose input may grow and say why you would choose the slower-growing method.