Which taxi is quicker?
Two taxi companies say they are the quickest. How can you decide? You could time them. But one runs on a busy day and one on a quiet day. The test is not fair.
It is the same for the methods a program uses. A fast computer makes a slow method look good. So we also count the work, and the count is the same on every computer.
Key words
| Word | What it means |
|---|---|
| Metric | A measure you use to compare things. |
| Execution time | How long the algorithm takes to run. |
| Memory space | How much memory the algorithm needs. |
| Comparisons | How many times two values are checked against each other. |
| Best case | The situation where the algorithm does the least work. |
| Worst case | The situation where the algorithm does the most work. |
| Average case | A typical situation, somewhere between the best and the worst. |
| Algorithm | A set of steps to solve a problem. |
| Linear search | Look at each item in turn from the start. |
| Binary search | Look at the middle of a sorted list and keep one half. |
| Bubble sort | Swap neighbours that are in the wrong order, pass after pass. |
| Insertion sort | Slide each item into its place in the sorted part. |
| Merge sort | Split the list, sort the parts, then merge them. |
The cells students fill in are left blank in this preview.
Three ways to measure
We compare algorithms with three metrics.
Memory space: how much extra memory it needs. Execution time: how long it takes. Number of comparisons: how many checks it makes. This is the fairest, because it does not depend on how fast the computer is.
Try it: count the checks
def linear_comparisons(items, target):
comparisons = 0
for item in items:
comparisons = comparisons + 1
if item == target:
return comparisons
return comparisons
numbers = []
for n in range(1, 101):
numbers.append(n)
print("Best case:", linear_comparisons(numbers, 1))
print("Worst case:", linear_comparisons(numbers, 100))
print("Not in the list:", linear_comparisons(numbers, 500))
print("Somewhere in the middle:", linear_comparisons(numbers, 50))
Worked example: searching 100 items
| Algorithm | Best case | Worst case | Average case |
|---|---|---|---|
| Linear search | 1 check: the target is first | 100 checks: the target is last or missing | About 50 checks: half the list |
| Binary search | 1 check: the target is in the middle | 7 checks | About 6 checks: near the worst case |
The cells students fill in are left blank in this preview.
Best, worst and average case
The same algorithm can be quick or slow, depending on the data. The best case is the lucky data. The worst case is the unlucky data. The average case is what you expect most days.
We do not need maths to find them. Ask: what data would make this algorithm do the least work? What data would make it do the most?
Quick check: name the case
Have a go
Quick check: name the case
3 questionsYour answers are marked here and are not kept. A college account keeps every student’s marks.
Try it: count the sort
def bubble_comparisons(items):
numbers = items
comparisons = 0
pairs = len(numbers) - 1
swapped = True
while swapped and pairs > 0:
swapped = False
for i in range(pairs):
comparisons = comparisons + 1
if numbers[i] > numbers[i + 1]:
temp = numbers[i]
numbers[i] = numbers[i + 1]
numbers[i + 1] = temp
swapped = True
pairs = pairs - 1
return comparisons
print("Already sorted:", bubble_comparisons([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]))
print("Reversed:", bubble_comparisons([10, 9, 8, 7, 6, 5, 4, 3, 2, 1]))
The cases for sorting 10 items
| Algorithm | Best case | Worst case | Extra memory |
|---|---|---|---|
| Bubble sort | 9 comparisons: already sorted | 45 comparisons: in reverse order | Almost none |
| Insertion sort | 9 comparisons: already sorted | 45 comparisons: in reverse order | Almost none |
| Merge sort | About 15 comparisons | About 25 comparisons | A whole new list is made at each merge |
The cells students fill in are left blank in this preview.