Big-O, measured
Big-O answers one question: if the input doubles, what happens to the running time? It ignores constants and machine speed and describes the shape of growth. That shape decides whether code that takes 1 ms on your test data takes 2 ms or 3 hours in production. Here every class is measured, not just asserted.
Delivering parcels
Opening your own front door takes the same time however many parcels exist: O(1). Delivering one parcel to each of n houses: O(n). Every house sending a parcel to every other house: O(n²). Finding a house number on a sorted street by halving the search each time: O(log n). Double the town, and the first stays the same, the second doubles, the third quadruples, and the last adds a single step.
1. The classes you will meet
| Class | Name | Typical operation | n = 1,000,000 → roughly |
|---|---|---|---|
| O(1) | constant | dict lookup, list index, append | 1 step |
| O(log n) | logarithmic | binary search, heap push/pop | 20 steps |
| O(n) | linear | one pass, x in list, sum | 10⁶ steps |
| O(n log n) | linearithmic | good sorting (sorted), merge sort | 2×10⁷ steps |
| O(n²) | quadratic | all pairs, nested loops over the same data | 10¹² steps: hours |
| O(2ⁿ) | exponential | all subsets, naive recursion | impossible beyond n ≈ 40 |
2. Measured on this machine
import bisect
import timeit
def constant(data): return data[len(data) // 2]
def logarithmic(data): return bisect.bisect_left(data, len(data) // 3)
def linear(data): return sum(data)
def linearithmic(data): return sorted(data, reverse=True)
def quadratic(data): # all pairs of a small slice (the full data would take hours)
part = data[:len(data) // 200]
return sum(1 for a in part for b in part if a < b)
print(f"{'n':>9} {'O(1)':>9} {'O(log n)':>9} {'O(n)':>9} {'O(nlogn)':>9} {'O(n²)':>9} (ms per call)")
for n in [100_000, 200_000, 400_000]:
data = list(range(n))
row = [timeit.timeit(lambda f=f: f(data), number=3) / 3 * 1000
for f in (constant, logarithmic, linear, linearithmic, quadratic)]
print(f"{n:>9,} " + " ".join(f"{t:9.3f}" for t in row))
Read the columns top to bottom. As n doubles, O(1) and O(log n) stay flat (they are too fast to measure meaningfully), O(n) roughly doubles, O(n log n) slightly more than doubles, and O(n²) roughly quadruples. (The quadratic column pairs up only 1/200 of the data: 500, 1,000 and 2,000 items. On all 400,000 items it would need 80 billion comparisons, about an hour.)
3. Working out Big-O from code
for x in data: # O(n)
total += x # × O(1) → O(n)
for x in data: # O(n)
for y in data: # × O(n) → O(n²)
...
for x in data: ... # O(n)
for y in data: ... # + O(n) → O(n) (sequential adds)
while n > 1: # halve each time
n //= 2 # → O(log n)
for x in data: # O(n)
if x in other_list: # × O(m) hidden! → O(n·m)
...
Drop constants and smaller terms
O(3n + 50) is O(n); O(n² + n) is O(n²). Big-O describes growth for large n, where the biggest term dominates. But constants still matter in practice. Between two O(n) solutions, the one doing a tenth of the work per item is ten times faster, and profiling (Advanced Python lesson 18) is how you find it.
Watch for hidden loops
x in list, list.index, list.remove, list.insert(0, …),
slicing and str concatenation in a loop are all O(n) inside what looks like one line.
Lesson 03 lists them.
4. Amortised O(1): why append is fast
import sys
data, sizes = [], []
last = sys.getsizeof(data)
for i in range(64):
data.append(i)
size = sys.getsizeof(data)
if size != last: # the underlying array was reallocated
sizes.append((len(data), (size - 56) // 8))
last = size
print("resized at length -> new capacity:", sizes)
A Python list over-allocates: when full, it grows by about 1/8 plus a little (capacities 4, 8, 16, 24, 32, 40, 52, 64 above), copying the elements into the bigger block. Most appends are a single write, and only occasionally is there an O(n) copy. Averaged over many appends, the cost per append is constant: amortised O(1). The same idea makes dicts and sets fast as they grow (lesson 09).
5. Space complexity and the time–space trade
def has_duplicate_quadratic(nums): # O(n²) time, O(1) extra space
return any(nums[i] == nums[j] for i in range(len(nums)) for j in range(i + 1, len(nums)))
def has_duplicate_sorted(nums): # O(n log n) time, O(n) space (sorted copy)
s = sorted(nums)
return any(a == b for a, b in zip(s, s[1:]))
def has_duplicate_set(nums): # O(n) time, O(n) space
return len(set(nums)) != len(nums)
import timeit
nums = list(range(3_000)) + [42]
for f in (has_duplicate_quadratic, has_duplicate_sorted, has_duplicate_set):
print(f"{f.__name__:26} {f(nums)} {timeit.timeit(lambda: f(nums), number=3) / 3 * 1000:9.2f} ms")
6. Best, worst and average case
Big-O usually describes the worst case. Some algorithms differ a lot between cases: linear search is O(1) if the item is first and O(n) if it is last or missing; quicksort is O(n log n) on average and O(n²) in its worst case (lesson 11); a dict lookup is O(1) on average and O(n) in a pathological collision case (lesson 09). When someone quotes a complexity, ask which case they mean.
Recap
- Big-O is the growth shape: what doubling n does to time or memory.
- O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). The jump from n log n to n² is where programs die.
- Nested loops multiply, sequential steps add, halving gives log n; watch for hidden O(n) calls.
- Amortised O(1): occasional expensive resizes averaged over many cheap operations.
- Trade space for time deliberately, and say which case (worst/average) you mean.
Checkpoint
for x in a: if x in b: count += 1, where a and b are lists of length n. Complexity?
b to a set once (O(n)), and each lookup becomes O(1), giving O(n) overall.