Counting steps as a function of input size

Step 1 Warm-up recall

From Module 4: worst case comparisons for linear search on 50 items?

Your answer

Private: nothing you type here is sent or stored.

Step 2 Learning goal

By the end of this lesson you can:

• define input size and basic step (Foundation);
• count steps for a simple method (Core);
• write the count as a formula in n (Core).

Step 3 A familiar example

Timing a method on your own computer tells you about your computer. Counting its steps tells you about the method, and the count does not change when the computer does.

Step 4 Clear explanation

The input size, written n, is the amount of data a method must handle, such as the number of items in a list. A basic step is one simple action, such as one comparison or one addition. The cost of a method is the number of basic steps it takes, written as a formula in n.

For example, to add n numbers you need n − 1 additions, because the first addition joins two numbers and each later one adds one more.

Another example: to compare every pair in a list of n items, each item is compared with each later item, giving (n − 1) + (n − 2) + … + 1 comparisons, which equals n × (n − 1) ÷ 2. For 10 items that is 45 comparisons, the same count seen in the sorting methods of Module 4. Counting steps lets you compare methods without a stopwatch, which is why the entry on the algorithm treats cost as part of what a method is.

Step 5 Worked example (4 marks)

How many comparisons does it take to compare every pair among 6 items?

1. Use n × (n − 1) ÷ 2 with n = 6. (1 mark)
2. 6 × 5 = 30. (1 mark)
3. 30 ÷ 2 = 15. (1 mark)
4. Answer: 15 comparisons. (1 mark)

Step 6 Learner practice (instant-marked)

Step 7 Recap

• Cost is a count of basic steps.
• Write the count as a formula in n.
• Counts compare methods fairly on any computer.

Step 8 Exit ticket (ungraded)

Count the pair comparisons for 8 items.

Your answer

Private: nothing you type here is sent or stored.

Step 9 Go further (Extension)

Read the entry on the algorithm and find one other measure of cost besides steps.