Code & Robots, level 10
📈 How Fast Does It Grow?
How can you tell whether a program will still be fast when its data gets huge?
- How can you tell whether a program will still be fast when its data gets huge? Computer scientists answer by counting steps instead of timing a stopwatch, because a stopwatch depends on how fast one particular computer happens to be. The question they ask is how the number of steps grows as the input grows. Take linear search, which checks the items in a list one at a time until it finds its target. On a list of 1,000 items it might need as many as 1,000 checks, and on a list of 2,000 items it might need as many as 2,000. The number of steps grows at the same rate as the list, so this kind of growth is called linear: double the input, and the work roughly doubles as well.
- Binary search, which works only on a sorted list, grows far more slowly. Each check compares the target with the middle item and throws away half of what remains, so 1,000 items shrink to 500, then 250, then 125, and so on. After about 10 checks only one item is left, since 2 multiplied by itself 10 times is 1,024. Doubling the list to 2,000 items adds just one more check, because a single extra cut in half brings 2,000 back down to 1,000. This pattern is called logarithmic growth, and the gap between it and linear growth widens dramatically with every doubling of the input. A sorted list of about a million items needs only about 20 checks, which explains why searching a sorted list stays remarkably fast even when the list becomes enormous.
- Programmers describe growth with a shorthand called Big-O notation, which the NIST Dictionary of Algorithms and Data Structures calls a theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n. Linear search is written O(n), and binary search is written O(log n). Some algorithms grow even faster than linear ones. A program that pairs each item in a list with every item in the same list, using one loop inside another, takes n times n steps, written O(n squared), so 1,000 items need a million steps. Big-O deliberately ignores small details and concentrates on the overall shape of the growth, because that shape matters most once the inputs become very large.
Try it at home: Play a number-guessing game from 1 to 1,000, answering only higher or lower, and see if halving each time finds it in about ten guesses.
Questions and answers
How Fast Does It Grow?
- Why do computer scientists count steps instead of using a stopwatch? A stopwatch depends on the computer's speed (Counting steps compares algorithms fairly on any computer.)
- 📈 When doubling the input roughly doubles the work, the growth is called… linear
- Binary search works only on a list that is… sorted (Binary search throws away halves by comparing with the middle, so the list must be in order.)
- 🔢 About how many checks does binary search need on a sorted list of 1,000 items? About 10 (2 multiplied by itself 10 times is 1,024, so about 10 cuts reach one item.)
- Growth where doubling the input adds only one more step is called… logarithmic growth
- 🔍 About how many checks does binary search need on a sorted list of about a million items? About 20 (2 multiplied by itself 20 times is about a million, so about 20 cuts reach one item.)