Comparing Algorithm Efficiency
Learn Comparing Algorithm Efficiency for GCSE Computer Science with this free worksheet and full mark scheme — Foundation and Higher exam-style questions with worked answers for AQA GCSE Computer Science (8525). Algorithms can be compared by how much time and memory they need for a given input size.
Free downloads
These worksheets and mark schemes are original, written for Virtus Academy and checked against the current AQA specification. Every worksheet comes with a full mark scheme.
Topic overview
Algorithms that produce the same result can differ greatly in how much time and memory they use, and comparing them is a required skill.
Time is usually measured by counting the operations needed, such as comparisons or swaps, rather than by timing in seconds — seconds depend on the hardware, whereas operation counts do not.
The comparisons required are specific. Linear search works on unsorted lists but needs up to n comparisons; binary search needs at most about log n but requires sorting first. Bubble sort is simple and uses little memory but is slow on large lists; merge sort is much faster but needs extra memory. The right choice depends on the list size, whether it is already sorted, and how often it will be searched.
Revision notes
Measuring efficiency
Count the operations required — comparisons, swaps or passes — rather than timing in seconds.
Seconds depend on the hardware running the code, so they cannot be used to compare algorithms fairly. Operation counts are independent of the machine.
Time versus memory
An algorithm may be fast but memory-hungry, or slow but memory-efficient.
Merge sort is faster than bubble sort but needs extra memory for sublists. Which matters more depends on the situation — a device with limited memory may prefer the slower algorithm.
Choosing an algorithm
Consider the size of the data, whether it is already sorted, and how often the operation will be repeated.
A large sorted list searched frequently favours binary search. A small unsorted list searched once favours linear search, because sorting first would cost more than it saves.
Key points
- Efficiency compares time and memory use.
- Count operations rather than timing in seconds.
- Operation counts are independent of hardware.
- Faster algorithms may use more memory.
- Binary search needs a sorted list.
- The best choice depends on the situation.
Worked examples
Example 1
Explain why algorithms are compared by counting operations rather than timing them in seconds. [2 marks]
Working
Example 2
A large sorted list will be searched many times. State which search algorithm is better and why. [2 marks]
Working
Example 3
Explain one situation where bubble sort may be preferred to merge sort. [2 marks]
Working
Common mistakes
Comparing algorithms by timing them.
Timings depend on hardware; count operations instead.
Assuming the faster algorithm is always better.
Memory use and the cost of sorting also matter.
Forgetting the sorting cost for binary search.
It must be included when the list is unsorted.
Giving a choice without justification.
Always say why the algorithm suits the situation.
Exam tips
- Count operations, not seconds.
- Consider memory as well as speed.
- Include sorting cost when comparing searches.
- Justify every algorithm choice with the situation.
Key terms
- Efficiency
- How much time and memory an algorithm uses.
- Operation
- A single step such as a comparison or swap.
- In place
- Working without needing significant extra memory.
- Trade-off
- Gaining in one respect at the cost of another.
Related topics
Written and reviewed against the current AQA specification. Spotted an error? Let us know.