Evaluating algorithm efficiency

Algorithms · Efficiency

Same list, same target: which search does less work?

Eight planets in alphabetical order, and we're looking for Venus, the last one. Steps 1 to 8 are linear search; steps 9 to 12 are binary search. The highlighted line is the planet being compared with Venus.

Before you press Next: how many comparisons do you think each search will need to find Venus?

 1  Earth
 2  Jupiter
 3  Mars
 4  Mercury
 5  Neptune
 6  Saturn
 7  Uranus
 8  Venus

What you need to know

• An algorithm is a set of step-by-step instructions to solve a problem. Describing how two algorithms differ lets you recognise when one is more suitable than another.
• The efficiency of searching algorithms is compared by the number of comparisons. The worst case is the highest number of comparisons possible on a given list.
• Linear search checks each item one at a time. In the worst case every item is compared, so doubling the list doubles its worst case. It works on ordered or unordered data.
• Binary search discards half of the remaining data with each comparison, until the item is found or the data runs out. Doubling the list adds at most one comparison. The items must be in order.
• On a sorted list of eight planets: linear search's worst case (Venus) is 8 comparisons; binary search's worst case is 4.
• Linear search is simpler to write; binary search is longer and more complex because the algorithm can take different paths. Which search suits best depends on the data and context.
• Tracing an algorithm with a trace table, which tracks the values of variables and the flow of execution step by step, helps you check how efficient it is.
• Bubble sort compares neighbouring items and swaps them if they're in the wrong order. Each trip through the list is a pass, and a pass makes (number of items − 1) comparisons.
• Bubble sort is one of the slowest sorting algorithms, especially on large data. Improve it by stopping when a pass makes no swaps, and by making one fewer comparison after each pass (the largest item has reached its final place).
• Choosing a sorting algorithm depends on factors such as efficiency on large data, how easy it is to implement and test, how much memory it needs, and how the data is formatted.

The big picture

Algorithms doing the same job can do very different amounts of work. For searching, count the comparisons in the worst case: on a sorted list of eight planets, linear search needs 8 and binary search needs 4, because each of its comparisons discards half of what's left. Double the list and linear search's worst case doubles, while binary search needs at most one more. But binary search needs ordered data and is harder to write, so the better choice depends on data and context. Bubble sort is one of the slowest sorting algorithms; stopping after a no-swap pass, and making one fewer comparison each pass, makes it more efficient.

⚠ Watch out

Thinking that doubling the list doubles binary search's comparisons too. Only linear search's worst case doubles; binary search needs at most one more comparison, because each comparison halves what's left.

Memory hook

Double the list: linear DOUBLES, binary adds ONE. Then ask the second question: is the data in order?

Check yourself

A sorted list has 32 items. What's linear search's worst case, and how many more comparisons might binary search need than for 16 items? Give one reason to still choose linear search.