Unit 4
Algorithms and efficiency.
Comparing algorithms without a stopwatch: four ways to sort, searching by halving, and big-O notation.
Before this unit
- Bits and data
- Exponents and logarithms Mathematics
The unit, lesson by lesson
Lessons
4 lessons · 22 practice questions · about 2 hours
The steps of an algorithm
What an algorithm is, through one way to sort: bubble sort compares neighbours and swaps them, pass after pass. Count the comparisons and swaps, and see how the starting row changes the work.
Comparing sorts
Four methods for one problem: bubble, insertion, merge and quicksort. Measure how many comparisons each makes on the same row, find that the number of swaps is fixed, and see that even a fast method has a worst case.
Searching and halving
Two ways to find a name in a list: check them one by one, or open the middle and throw half away. Why binary search needs a sorted list, and how the base-two logarithm counts the halvings it needs.
Growth rates and big-O
What happens to the work when the list doubles: bubble sort grows like the square of the length, and merge sort only a little faster than the length itself. The graph that compares them, big-O notation, and why a good algorithm beats a fast computer.