Counting steps
In lesson 1-1 the list did 10,000 checks and the dict did 1. We need a language for that difference, one that does not depend on how fast your laptop is. That language is Big-O notation.
The idea: instead of measuring seconds, count the steps a piece of code takes as a function of the input size, which we call n. Then keep only the part that grows.
- Reading
names[500]is one step no matter how long the list is. We write O(1), constant time. - Scanning a list of n items is about n steps: O(n), linear time.
- Comparing every item to every other item is n × n steps: O(n²), quadratic time.
Let's count for real.
Code exercise · python
Run this. `count_linear` walks one loop, `count_pairs` nests two loops. Watch what happens to each count when n grows 10× : the linear count grows 10×, the pairs count grows 100×.
Dropping the noise
Big-O keeps only the fastest-growing term and ignores constant factors, because for large n nothing else matters.
- 3n + 12 steps → O(n). The 3 and the 12 disappear.
- n²⁄2 + n steps → O(n²). Half of a quadratic is still quadratic.
- 5 steps, always → O(1).
Why so ruthless? At n = 1,000,000, an O(n) pass is a million steps and an O(n²) pass is a trillion. A computer doing 100 million steps per second finishes the first in 0.01s and the second in about 3 hours. Constant factors move that by 2× or 3×. The growth family moves it by hours.
| steps formula | Big-O |
|---|---|
| n + 500 | O(n) |
| 4n² + n | O(n²) |
| 7 | O(1) |
| n⁄2 | O(n) |
Quiz
A function does 2n + 10 steps for an input of size n. What is its Big-O?
Code exercise · python
Your turn. `triangle_steps(n)` should count the steps of a nested loop where the inner loop runs `i` times, not n times: `for i in range(n): for j in range(i): steps += 1`. Implement it and print n and the count for n in [10, 100, 1000]. Notice it is about n²⁄2, still O(n²).
Quiz
The triangle loop did n(n−1)⁄2 steps, about half as many as the full n² pair loop. Why do we still call it O(n²)?