Algorithm Performance

AQA 4.3.4 & 4.3.5 — Comparing algorithm performance

Retrieval: this sequence has now covered two searching algorithms (Linear Search, Binary Search) and two sorting algorithms (Bubble Sort, Insertion Sort). This final lesson compares them directly, using evidence rather than impressions — the Choose → Justify stage for everything you've learned in this sequence.

Comparing the searching algorithms

	Linear Search	Binary Search
Requires sorted data?	No	Yes
Worst case	Checks every item — O(n)	Halves the range each step — O(log n)
Best for	Small or unsorted lists, one-off searches	Large, already-sorted lists searched repeatedly

Comparing the sorting algorithms

	Bubble Sort	Insertion Sort
Core operation	Adjacent swaps, repeated passes	Shift-and-insert into a growing sorted partition
Best case (nearly sorted data)	Slow unless the early-stop optimisation is used	Naturally fast — few shifts needed
Worst case (reverse sorted)	Many swaps every pass	Many shifts for every item

Worked example — measuring, not guessing

Rather than assuming which sort performs better, you can count operations directly:

def bubble_sort_with_count(items):
    n = len(items)
    swap_count = 0
    for i in range(n):
        for j in range(n - 1 - i):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                swap_count += 1
    return items, swap_count

Running this on [1, 2, 3, 4, 5] (already sorted) gives 0 swaps. Running it on [5, 4, 3, 2, 1] (reverse sorted, the worst case) gives 10 swaps — for the same algorithm, the data alone changes the performance dramatically. This is exactly why "how fast is this algorithm?" is never a complete question without also asking "on what data?"

Justify it

For each scenario, justify which algorithm (from this sequence) is most appropriate:

Searching a customer database of 2 million sorted records, many times per second.
Sorting a leaderboard of 10 scores that's already almost in order, updated after every game.
Searching a shopping basket of 5 items that changes every time the customer adds something.

Cumulative retrieval — from Sequence 4

Sequence 4's Dictionaries lesson claimed that looking a record up by key in a dictionary is "effectively instant, regardless of how large the dictionary is," and promised this lesson would let you compare that claim against real evidence. You now can: Binary Search's O(log n) worst case still means a 2-million-record search takes several times longer than a 20-record one, because it has to keep halving a shrinking range — but a dictionary lookup by key doesn't scan or halve anything at all, so its performance barely changes as the collection grows. Using this, explain why a system that repeatedly looks records up by a known, unique ID (like a customer database keyed by customer ID) would be a stronger candidate for a dictionary than for even the most efficient searching algorithm covered in this sequence.

Challenge

Extend the operation-counting idea to insertion sort: modify insertion_sort so it also returns a count of how many shift operations occurred, then run it on both a sorted and a reverse-sorted list of the same size and compare the counts to bubble sort's.

Looking ahead: Sequence 6 (Computational Thinking) steps back from specific algorithms to the general thinking skills — abstraction, decomposition, pattern recognition — that let you design a new algorithm for a problem no one has given you a name for yet.

Learn