The Growth-Rate Family
The Growth-Rate Family: Why the Library Check Slows Down and Play Doesn't: O(1) and O(n), How Many Times Can You Halve a Million? O(log n), Why the Duplicates…
Updated
- Why the Library Check Slows Down and Play Doesn't: O(1) and O(n) (Novice): Tell a job whose work stays the same as the library grows from one whose work grows with it, and read their growth rates aloud: O(1), constant time, and O(n), linear time.
- How Many Times Can You Halve a Million? O(log n) (Novice): Find one song among a million sorted titles in about 20 looks instead of a million, and name the growth rate that makes it possible: O(log n), logarithmic time.
- Why the Duplicates Button Crawls: O(n²) (Novice): Find out why a "find duplicates" button that takes a second at 10,000 songs takes about half a minute at 50,000, spot the loop-inside-a-loop that causes it, and name its growth rate: O(n²), quadratic time.
- Sorting a Million Songs, and the Playlist You Can't Compute: O(n log n) and O(2ⁿ) (Apprentice): See why a good sort handles a million songs in under a second while the obvious ways take most of a day, and why a playlist that fills exactly 60 minutes can't be found by trying every combination: O(n log n) and O(2ⁿ).
- Will It Survive a Million Users? The Doubling Table (Novice): One table puts all six growth rates side by side at 10, 1,000 and 1,000,000 items, and shows why the growth rate of your code matters far more than the speed of your computer.