GCSE-ready- Home
- Lessons
- GCSE & IGCSE Computer Science
- Evaluating algorithms and test data
Evaluating algorithms and test data
🎬 The doodle video for this lesson is coming soon. Subscribe on YouTube to see it first.
Two algorithms can solve the same problem but one may be far quicker or use far less memory. Good test data proves an algorithm really works.
Measuring efficiency
Count the number of comparisons, the number of passes through a loop, and the memory used.
Linear search on n items: up to n comparisons.
Binary search halves the list each time, so it needs far fewer comparisons on large sorted lists.
Merge sort is faster than bubble sort on big lists but needs extra memory for the sub-lists.
Linear search on n items: up to n comparisons.
Binary search halves the list each time, so it needs far fewer comparisons on large sorted lists.
Merge sort is faster than bubble sort on big lists but needs extra memory for the sub-lists.
Test data
Fitness for purpose
An algorithm is fit for purpose if it gives the correct output for all test data and meets the requirements.
Use logical reasoning: trace it with normal, boundary and erroneous data and compare with the expected results.
Use logical reasoning: trace it with normal, boundary and erroneous data and compare with the expected results.
How many comparisons does a binary search make to find 31 in [3, 8, 12, 19, 24, 31, 40]?
- Middle item is 19. 31 > 19, so keep the right half [24, 31, 40].
- Middle of that half is 31. Found.
Answer: 2 comparisons
Efficiency is judged by comparisons, loop passes and memory. Test with normal, boundary and erroneous data. Binary search beats linear search on big sorted lists; merge sort is fast but uses more memory.
The interactive lesson includes the diagrams for this topic.
Check you have got it
Answer 7 quick questions with instant marking. If you get one wrong, GCSE-ready shows you why and gives you another go. It is free, and you do not need an account.