Theory answers "how does time grow as n grows?", while measurement shows the actual time on an actual machine. A good engineer combines both: derive an expectation from analysis and check it by measuring. In this lesson we build small tools for checking complexity empirically.
The measuring protocol
- Pick sizes of
nand keep doubling them:n, 2n, 4n, .... - Prepare the input data outside the timer.
- Repeat several times for each size and take the minimum: it is the least noisy.
- Compute the ratio
T(2n) / T(n)or the slope on a log-log scale. - Compare the result with the theoretical expectation.
| Complexity | Expected T(2n) / T(n) | log-log slope |
|---|---|---|
O(1) | ≈ 1 | 0 |
O(log n) | ≈ 1 (slightly more) | ≈ 0 |
O(n) | 2 | 1 |
O(n log n) | a bit above 2 | a bit above 1 |
O(n^2) | 4 | 2 |
O(n^3) | 8 | 3 |
O(2^n) | T(n + 1) / T(n) = 2 | not a straight line |
A benchmark function and ratios
bench returns the best of the repeats. ratio shows how many times the time grows when the size doubles. Results depend on the machine, so we check the answer against a range, not exact seconds.
import random
from time import perf_counter