Race the Algorithms

Two ways to the same answer

You have already met two algorithms that find an item in a list, and you know one of them is better. This topic is about being able to prove it. More than one algorithm can solve the same problem, and when two both work the question becomes which is more efficient. Here is the sentence this specification is built on: an answer that says one algorithm is faster earns nothing, and an answer that gives a count of steps earns the mark. So this module is about turning an opinion into a number, and then about the thing that number is really telling you.

Words for comparing algorithms

Six terms. Notice that none of them is a piece of notation: at this level efficiency is described in words and in counts.

Term to what it counts

Worst case for a linear search

A linear search checks each item in turn until it finds what it is looking for. On a list of 15 items, what is the largest number of comparisons it could need?

Worst case for a binary search

A binary search on the same sorted list of 15 items halves the range each time. What is the largest number of comparisons it could need?

Doubling the list

The list grows to 31 items. What is the largest number of comparisons a linear search could now need?

It is faster earns nothing

Put the three numbers together and something appears that no opinion could have told you. On 15 items the linear search needs at most 15 comparisons and the binary search at most 4. Roughly double the list to 31 and the linear search needs at most 31, while the binary search needs at most 5. The list doubled; one count doubled with it and the other went up by one. That is the difference between the two algorithms, and it is a difference you can only state because you counted. When a question asks which is more efficient, give it exactly like that: two counts and what happens to them when the list grows.

Two ways to find the largest

Efficiency is not only about searching. Here are two algorithms that both correctly find the largest value in a list, to show that working is not the same as being sensible.

What a justification needs

A question asks which of two algorithms is more efficient. Select the TWO things your answer must contain.

• A count of the steps or comparisons each one takes
• What happens to those counts when the input gets bigger
• A clear statement that one of them is faster than the other
• The full code for both algorithms, written out correctly

Growth in a paragraph

When two algorithms both solve a problem, the more useful question is which is more _____. At this level you answer it by counting _____ rather than by asserting that one is quicker. The input that makes an algorithm do the most work is called the _____ case. What matters most is not the count on one list but its _____, meaning what happens to it as the list gets larger. Doubling a list doubles the work for a linear search but adds only _____ comparison to a binary search.

Trace the comparisons

This algorithm counts how many comparisons a linear search makes. The value being looked for is at position 3. Fill in the blank cells.

A comparison, justified

Question: two algorithms both find an item in a sorted list. Explain which is more efficient. Model answer: a linear search checks each item in turn, so on a list of 15 items it needs at most 15 comparisons. A binary search halves the range each time, so on the same list it needs at most 4. If the list grows to 31 items, the linear search needs at most 31 comparisons while the binary search needs at most 5. The binary search is therefore more efficient, and the important point is not that it used fewer comparisons on one list but that doubling the list roughly doubled the work for the linear search while adding only one comparison to the binary search. The binary search does require the list to be sorted first, so it is not always the available choice. Note that the answer never says faster on its own. It gives counts, says what happens when the input grows, and then names the condition the better algorithm depends on.

Which justification scores

Three of these sentences would earn credit in an efficiency question. Select the ONE that would not.

• On a list of 15 items the linear search needs at most 15 comparisons.
• The binary search is faster, so it is obviously the better algorithm to use.
• Doubling the list adds only one comparison to the worst case of a binary search.
• The binary search needs the list to be sorted, which the linear search does not.

Order the comparison

Put the steps of comparing two algorithms into the order you would work through them.

• Check that both algorithms actually solve the same problem
• Choose what you will count, such as comparisons, and use the same unit for both
• Work out the worst case for each on a list of a given size
• Work out what happens to each count when the list gets bigger
• State which is more efficient, giving the counts as the reason
• Name any condition the better algorithm depends on

Comparing like for like

A student says the linear search is better because it can find the item in one comparison if it is first, while the binary search needed four. What is wrong with that?

• It compares the best case of one against the worst case of the other
• Nothing, because a linear search really can find an item in one comparison
• The binary search never needs four comparisons on a list that size
• The linear search cannot be used on a sorted list at all

Justify the better algorithm

Two algorithms both find a name in a list of contacts. One checks each entry in turn; the other halves a sorted list each time. Explain which is more efficient and justify your answer.

• State what you are counting, and say why you use the same unit for both
• Give the worst case for each on a list of 15 items
• Give the worst case for each when the list grows to 31 items
• Explain what those two pairs of numbers show about how each algorithm grows
• Explain why comparing the best case of one with the worst case of the other proves nothing
• Name one condition the more efficient algorithm depends on