Fine with a hundred, frozen with a million
A new app works perfectly when ten friends test it. On launch day a hundred thousand people sign up, and it freezes.
Nothing in the code changed. Only the amount of data did. Some algorithms cope with growth and some do not, and you can tell which before launch day.
By the end of this lesson
Note
I can compare algorithms by how their time grows.
Key words
| Word | What it means | Example |
|---|---|---|
| Input size | how much data an algorithm is given, called n | |
| Big O | a way of saying how the steps grow as n grows | O(n) |
| Constant time | the same steps whatever n is, O(1) | |
| Linear time | steps grow in step with n, O(n) | |
| Quadratic time | steps grow with n times n, O(n²) | |
| Logarithmic time | one more step each time n doubles, O(log n) |
The cells students fill in are left blank in this preview.
Count steps, not seconds
Seconds depend on the machine. A gaming PC is faster than an old laptop, so a time on its own says little.
Instead, count the steps an algorithm takes for an input size n. One loop over n items takes n steps. A loop inside a loop takes n steps for every one of n items: n times n.
Counting steps for three sizes
# Count the steps instead of timing them.
for n in [10, 20, 40]:
single = 0
for a in range(n):
single = single + 1
nested = 0
for a in range(n):
for b in range(n):
nested = nested + 1
print("n =", n, "one loop:", single, "loop in a loop:", nested)
# Add 80 to the list of sizes.
# Predict both counts before you press Run.
Big O names the shape of growth
Big O keeps only the part that matters when n is large. A loop in a loop is O(n²), however much work sits inside it.
Reading one list item by its index is O(1). A linear search is O(n). A binary search is O(log n): doubling n adds one step. Bubble sort is O(n²). Merge sort is O(n log n), between the two.
Worked example: steps for each shape
| n | O(1) | O(log n) | O(n) | O(n²) |
|---|---|---|---|---|
| 8 | 1 | 3 | 8 | 64 |
| 16 | 1 | 4 | 16 | 256 |
| 1,024 | 1 | 10 | 1,024 | 1,048,576 |
The cells students fill in are left blank in this preview.
A common mistake
Warning
Many people think Big O tells you how many seconds a program takes. It only tells you how the time grows as n grows. For a tiny list an O(n²) sort can even win. Big O matters when n is large, which is when it hurts.
The doubling test in the lab
You can test the shape of an algorithm without reading its code. Time it, double n, and time it again.
If the time doubles, it is linear. If it goes up about four times, it is quadratic. The next four Runs time one loop at 1,000 and 2,000 items, then a loop in a loop at 300 and 600.
One loop over 1,000 items
docker exec jupyter python3 -m timeit -s "data = list(range(1000))" "for x in data: pass"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
One loop over 2,000 items
docker exec jupyter python3 -m timeit -s "data = list(range(2000))" "for x in data: pass"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A loop in a loop over 300
docker exec jupyter python3 -m timeit -s "data = list(range(300))" "for a in data:" " for b in data: pass"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A loop in a loop over 600
docker exec jupyter python3 -m timeit -s "data = list(range(600))" "for a in data:" " for b in data: pass"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A timing chart shows the shape
A chart makes growth easy to see. The notebook cell below times both shapes for four sizes and puts the times in a DataFrame.
Then it draws one line for each. A straight line is linear. A line that curves upwards faster and faster is quadratic.
Type this in your notebook: a timing chart
import time
import pandas as pd
def one_loop(n):
total = 0
for a in range(n):
total = total + a
return total
def loop_in_loop(n):
total = 0
for a in range(n):
for b in range(n):
total = total + 1
return total
rows = []
for n in [250, 500, 1000, 2000]:
start = time.perf_counter()
one_loop(n)
middle = time.perf_counter()
loop_in_loop(n)
end = time.perf_counter()
# Keep the times in milliseconds.
rows.append({"n": n, "one loop": (middle - start) * 1000, "loop in a loop": (end - middle) * 1000})
times = pd.DataFrame(rows).set_index("n")
print(times.round(3))
times.plot(marker="o", title="Time in ms against n")
Going further: time your own searches
Go back to the notebook from lesson 1. Time linear_search and binary_search for lists of 250,000, 500,000 and a million numbers.
Put the times in a DataFrame and draw them, as in this lesson. Which line is nearly flat, and which Big O does each line show?