Fine on Monday, stuck by Friday
A report runs in one second on a test file of 100 customers. On the real file of 100,000 customers it runs all night.
Nothing is broken. The code takes more steps for every extra customer, and the steps grow fast.
This lesson shows how to see that coming before it happens.
By the end of this lesson
Note
I can compare how two algorithms grow with more data.
Key words
| Word | What it means | Example |
|---|---|---|
| Algorithm | steps that solve a problem | |
| Step | one small piece of work, such as one compare | |
| Growth | how the steps change as the data gets bigger | |
| Big O | a short label for growth | O(n) |
| n | the number of items in the data | |
| Nested loop | a loop inside another loop |
The cells students fill in are left blank in this preview.
Count the steps, not the seconds
Seconds depend on the computer. Steps do not. So we compare algorithms by counting steps.
Then we ask a better question: what happens to the steps when the data gets ten times bigger?
That answer is the algorithm's growth. It tells you whether the code will cope with real data.
Try it: two ways to find a repeat
# Two ways to check a list of order ids for a repeat.
def repeats_by_pairs(ids):
steps = 0
for first in range(len(ids)):
for second in range(first + 1, len(ids)):
steps = steps + 1 # compare every pair
return steps
def repeats_by_set(ids):
steps = 0
seen = set()
for one in ids:
steps = steps + 1 # one look in the set per id
seen.add(one)
return steps
for size in [10, 100, 1000]:
ids = list(range(size))
print(size, "ids:", repeats_by_pairs(ids), "steps by pairs,",
repeats_by_set(ids), "steps by set")
# Add 2000 to the list of sizes, then press Run.
Worked example: the steps you just counted
| Ids | Steps by pairs | Steps by set |
|---|---|---|
| 10 | 45 | 10 |
| 100 | 4,950 | 100 |
| 1,000 | 499,500 | 1,000 |
The cells students fill in are left blank in this preview.
Four common kinds of growth
Most code you meet grows in one of four ways. Developers give each a Big O label, where n is the number of items.
A dictionary lookup stays the same: O(1). Binary search adds one step when the data doubles: O(log n). Linear search grows in step with the data: O(n). A nested loop over the same data grows with the square: O(n²).
Worked example: steps for each kind of growth
| Items | O(1) lookup | O(log n) binary search | O(n) linear search | O(n²) every pair |
|---|---|---|---|---|
| 10 | 1 | 4 | 10 | 100 |
| 1,000 | 1 | 10 | 1,000 | 1,000,000 |
| 1,000,000 | 1 | 20 | 1,000,000 | 1,000,000,000,000 |
The cells students fill in are left blank in this preview.
A common mistake
Warning
Many people think a faster computer fixes slow code. A computer twice as fast halves the time. But an O(n²) report on ten times the data takes a hundred times the steps. When data grows, change the algorithm, for example a nested loop for a set.
Trees and graphs come next
Two more structures appear in many jobs. A tree has one top item that branches out, like folders on a laptop or a company's reporting lines.
A graph is items joined by links, like delivery routes between depots or people who follow each other. Their searches build on what you learnt here.