The Big O race
Race a hash lookup, binary search, linear search, merge sort and bubble sort as the number of items grows from 8 to 1024. See some lines barely rise while bubble sort shoots up past half a million steps, and learn the Big O names for how each one grows.
Core concept
Big O describes how an algorithm's steps grow with the size of its input n: O(1) stays the same, O(log n) grows by one when n doubles, O(n) doubles, O(n log n) a little more than doubles, and O(n²) quadruples
Topic: Algorithm efficiency
Two programs can give the same answer but need very different amounts of work. Programmers describe this with Big O: how the number of steps grows as the input, n items, gets bigger. A hash table lookup takes about the same single step however big the table is: O(1). binary: Counting with only two digits, 0 and 1. Computers store everything this way. All key words search halves the list each time, so doubling n adds just one more step: O(log n). Linear search may look at every item: O(n), so doubling n doubles the work. Merge sort is O(n log n), a little more than doubling. Bubble sort compares every pair: O(n²), so doubling n makes four times the work. For 8 items the differences are small; for 1024 items they are enormous.
What you will learn
- Read the worst-case steps of five algorithms for a given n.
- Describe what happens to each count when n doubles.
- Match algorithms to their Big O names.
- Choose a suitable algorithm for a large input.
Before you start
- Know linear search, binary search and bubble sort.
Materials
- A calculator, to check the doubling
Equipment
- None
Procedure
- Run the race with 8 items.
- Run it with 1024 items and compare.
- Run it with 16 and then 32 items to see what doubling does.
- Answer the practice challenges.