Brainlag PlusMeasure efficiency by counting comparisons, read searches written as code, and complete trace tables.
Measuring efficiency
Two algorithms can solve the same problem with very different amounts of work.
At GCSE we compare them by counting steps, usually comparisons, in the worst case.
- Linear search on n items: up to n comparisons. Double the list, double the work.
- Binary search on n sorted items: halve n until nothing is left. Double the list, add one comparison.
- Time taken = number of steps × time for one step.
The rest of this lesson and its 7 practice questions are in Plus.
Screen 1 of 4, free to read.
- 7 exam-style questions, marked as you go, each with a worked solution
- Anything you get wrong is saved to your flashcards