Measuring speed
Use time.perf_counter() to time two duplicate-detection algorithms and watch O(n) vs O(n²) diverge on growing inputs.
- Use time.perf_counter() to time a function in Python
- Compare an O(n) and an O(n²) implementation on growing inputs
- Observe how quadratic growth becomes visible at moderate input sizes
Big-O growth rates are abstract until you can see the numbers diverge in front of you. The code below solves the same problem — "does this list contain any duplicates?" — two ways: once with nested loops (O(n²)) and once with a set (O(n)). Then it times both on inputs of increasing size.
The two implementations
The nested-loop version compares every pair of elements. If any pair matches, it
returns True. With n elements there are roughly n²/2 pairs — so the work grows
quadratically.
The set version makes a single pass. For each element it asks "have I seen this before?" The set answers that in O(1). If the element is already in the set we have a duplicate; otherwise we add it and continue. Total work: O(n).
Run it
time.perf_counter() returns a float in seconds measured by the highest
resolution clock available. Subtract two calls around the code you want to
measure; multiply by 1000 to convert to milliseconds. It measures wall time,
so results vary between runs — the ratio between slow and fast is what
matters, not the absolute numbers.
What you should see
At n=100 the slow version is probably under 1 ms — fast enough that you wouldn't notice in practice. At n=1 000 it starts to lag. At n=5 000 the slow version is doing roughly 12 500 000 comparisons; the fast version is doing 5 000. The timing gap should be obvious, and it widens steeply from there.
This is why Big-O matters: the slow version does not just "take longer" — it takes disproportionately longer as the input grows. A 50× input increase produces a ~2500× increase in work for O(n²) and only a ~50× increase for O(n).
The code to solve the problem is about the same complexity either way. The data structure — a set instead of a second loop — is the entire difference.
Where to go next
Next: Lab: algorithm practice — three small problems where you choose the right structure and apply the patterns from this module.
Big-O intuition
Big-O describes how an algorithm's work grows with input size. Learn to recognise O(1), O(n), and O(n²) by sight — no maths required.
Lab: algorithm practice
Three guided problems — most-common word, pair sums, and anagram check — each asking you to pick the right data structure and apply the patterns you have learned.