These are the notes for Python episode 33. Raju's loyalty report checks 20,000 orders against 20,000 registered customers and takes seconds, with no network and no waiting, so the threads and async of the last two episodes can't help. In this episode you measure code properly, invent Big-O notation to explain why the time grows the way it does, fix the report with a set, find slow functions in bigger programs with the cProfile profiler, and learn which built-ins and data structures are fast. Every program below ran for real (Python 3.13.18). Timings depend on your computer and vary between runs; compare patterns and ratios, not exact numbers.
The problem: a slow report
import time
customers = [9_000_000_000 + i * 7 for i in range(20_000)] # phone numbers
orders = [9_000_000_000 + i * 3 for i in range(20_000)]
start = time.perf_counter()
known = 0
for phone in orders:
if phone in customers:
known += 1
print("known customers:", known)
print(f"took {time.perf_counter() - start:.2f} s")
Output (one run):
known customers: 2858
took 2.21 s
Seconds of pure calculation for just 20,000 orders. A faster laptop might halve it; guessing at lines to change is just guessing. First, measure, and ask how the time grows with the data.
Measure first
time.perf_counter(): a high-resolution stopwatch for timing a block once.timeit.timeit(func, number=N): runsfuncN times and returns the total seconds. Repeating smooths out noise from other programs on your computer.- From a terminal:
python3 -m timeit "sum(range(1000))".
import time
def count_known(n):
customers = list(range(0, n * 7, 7))
orders = list(range(0, n * 3, 3))
start = time.perf_counter()
known = sum(1 for phone in orders if phone in customers)
return time.perf_counter() - start
for n in [2_000, 4_000, 8_000, 16_000]:
print(f"n = {n:>6}: {count_known(n):.3f} s")
Output (one run):
n = 2000: 0.016 s
n = 4000: 0.062 s
n = 8000: 0.312 s
n = 16000: 1.071 s
Every time n doubles, the time goes up about 4×. That pattern is the clue.
Big-O notation
Big-O describes how the number of steps an algorithm takes grows as the input size n grows. It ignores the exact speed of the computer and constant factors, and keeps only the growth.
| Big-O | Name | Real-life picture | Python examples | n = 1,000,000 → about |
|---|---|---|---|---|
| O(1) | constant | walk straight to hotel room 204 | d[key], x in a_set, lst[i], lst.append(x) |
1 step |
| O(log n) | logarithmic | a word in a dictionary: open the middle, halve again | binary search (bisect) on sorted data |
20 steps |
| O(n) | linear | a name in a messy register, page by page | x in a_list, one loop, sum, max, lst.index(x) |
1,000,000 steps |
| O(n log n) | linearithmic | sorting a pile of exam papers | sorted(), list.sort() |
20,000,000 steps |
| O(n²) | quadratic | for every order, read the whole register | a loop inside a loop over the same data | 1,000,000,000,000 steps |
Rules:
- Drop constants:
3n + 5steps is O(n). Big-O is about growth, not exact counts. - Keep the biggest term:
n² + nis O(n²). - Hidden loops count:
x in a_list,lst.index(x),lst.remove(x),lst.pop(0)andlst.insert(0, x)are all O(n). - Usually we talk about the worst case: the most steps for any input of size n.
The report: for each of n orders, in customers reads up to n items → n × n = O(n²), which is why doubling n multiplied the time by 4.
Binary search: O(log n) for real
import bisect, timeit
prices = list(range(0, 2_000_000, 2)) # 1,000,000 sorted prices
def linear(x):
return x in prices # checks one by one
def binary(x):
i = bisect.bisect_left(prices, x) # halves the list each step
return i < len(prices) and prices[i] == x
print(linear(1_999_998), binary(1_999_998))
t1 = timeit.timeit(lambda: linear(1_999_998), number=20)
t2 = timeit.timeit(lambda: binary(1_999_998), number=20)
print("linear:", round(t1, 3), "s")
print("binary:", round(t2, 6), "s")
Output (one run):
True True
linear: 0.278 s
binary: 1e-05 s
bisect.bisect_left(sorted_list, x)returns the position wherexis, or would be inserted, in a sorted list, by halving the search range each step (binary search).- A million items need about 20 halvings (2²⁰ ≈ 1,000,000); doubling the list adds just one step.
- Binary search only works on sorted data, and sorting costs O(n log n), so it pays off when you sort once and search many times.
The fix: a set
A set (episode 11) stores items by their hash, a number computed from the value that points straight to the item's slot. Checking x in a_set is O(1) on average, like walking to the hotel room.
import time
customers = [9_000_000_000 + i * 7 for i in range(20_000)]
orders = [9_000_000_000 + i * 3 for i in range(20_000)]
start = time.perf_counter()
customer_set = set(customers) # build it once
known = 0
for phone in orders:
if phone in customer_set:
known += 1
print("known customers:", known)
print(f"took {time.perf_counter() - start:.4f} s")
Output (one run):
known customers: 2858
took 0.0040 s
Same answer, hundreds of times faster: building the set is O(n), and n O(1) lookups are O(n). The whole thing went from O(n²) to O(n).
Build the set once, before the loop. if phone in set(customers): inside the loop rebuilds it on every order, which is O(n²) again and even slower than the list.
A dict works the same way when you need a value per key: name_by_phone = {c.phone: c.name for c in customers}, then name_by_phone.get(phone).
Profiling: which function is slow?
A profiler runs your program and records how much time each function takes. Python's built-in one is cProfile; pstats reads and sorts its results.
import cProfile, pstats
def load_orders():
return [9_000_000_000 + i * 3 for i in range(15_000)]
def find_known(orders):
customers = [9_000_000_000 + i * 7 for i in range(15_000)]
return [p for p in orders if p in customers]
def make_report(known):
return "\n".join(f"+91 {p}" for p in known)
def nightly_job():
known = find_known(load_orders())
report = make_report(known)
print("report lines:", len(known))
cProfile.run("nightly_job()", "stats")
profile = pstats.Stats("stats").get_stats_profile()
top = sorted(profile.func_profiles.items(),
key=lambda kv: kv[1].tottime, reverse=True)
for name, f in top[:3]:
print(f"{f.tottime:.3f} s {f.ncalls:>3} calls {name}")
Output (one run; the order of the small entries can change):
report lines: 2143
2.314 s 1 calls find_known
0.004 s 1 calls nightly_job
0.001 s 1 calls load_orders
cProfile.run("code", "stats")runs the code and saves the timings to a file calledstats.pstats.Stats("stats").get_stats_profile()(Python 3.9+) gives a profile whosefunc_profilesmaps each function name to its numbers:ncalls,tottime,cumtime,file_name,line_number.- We sort by tottime and print the top three.
find_knowntakes nearly all the time; speeding up the report would be wasted effort.
The classic full table, from print_stats:
pstats.Stats("stats").strip_dirs().sort_stats("tottime").print_stats(3)
ncalls tottime percall cumtime percall filename:lineno(function)
1 1.194 1.194 1.194 1.194 main.py:6(find_known)
1 0.001 0.001 0.001 0.001 main.py:3(load_orders)
2144 0.000 0.000 0.000 0.000 main.py:11(<genexpr>)
| Column | Meaning |
|---|---|
ncalls |
how many times the function was called |
tottime |
time spent inside the function itself, not counting functions it called |
percall |
tottime / ncalls (the second percall is cumtime / ncalls) |
cumtime |
total time including the functions it called (cumulative) |
filename:lineno(function) |
where the function is defined (strip_dirs() removes the folders) |
From a terminal you can profile any script without changing it:
python3 -m cProfile -s tottime app.py
Fast built-ins
Built-in functions (sum, min, max, sorted, len, any, all) and the collections types are written in C, so each step is far cheaper than a step of Python code. Same Big-O, smaller constant factor.
import timeit
bills = list(range(1_000_000))
def by_hand():
total = 0
for b in bills:
total += b
return total
print("for loop:", round(timeit.timeit(by_hand, number=10), 2), "s")
print("sum(): ", round(timeit.timeit(lambda: sum(bills), number=10), 2), "s")
Output (one run):
for loop: 0.19 s
sum(): 0.06 s
More one-liners:
from collections import Counter
orders = ["chai", "samosa", "chai", "toast", "chai", "samosa"]
print(Counter(orders).most_common(2))
customers = [("Ravi", 450), ("Asha", 1200), ("Neha", 800)]
print(sorted(customers, key=lambda c: c[1], reverse=True))
print(max(customers, key=lambda c: c[1]))
Output:
[('chai', 3), ('samosa', 2)]
[('Asha', 1200), ('Neha', 800), ('Ravi', 450)]
('Asha', 1200)
Counter(items)counts each value;.most_common(k)gives the top k.sorted(..., key=func)sorts by whatfuncreturns (episode 17);reverse=Truefor highest first.max/mintake akeytoo.- Joining strings:
",".join(names)is the standard way to build one string from many.
The queue trap: list.pop(0) vs deque
import time
from collections import deque
queue = list(range(100_000))
start = time.perf_counter()
while queue:
queue.pop(0) # take from the front
print(f"list.pop(0): {time.perf_counter() - start:.2f} s")
queue = deque(range(100_000))
start = time.perf_counter()
while queue:
queue.popleft()
print(f"deque.popleft(): {time.perf_counter() - start:.3f} s")
Output (one run):
list.pop(0): 0.78 s
deque.popleft(): 0.004 s
A list stores items side by side; removing the first one shifts every other item one place left, O(n) per pop, O(n²) for the loop. A deque ("deck", double-ended queue) adds and removes at both ends in O(1): append, appendleft, pop, popleft.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
if x in big_list inside a loop |
seconds for 20,000 items | O(n) lookup → O(n²) overall | big_set = set(big_list) once |
set(big_list) inside the loop |
slower than the list | rebuilt every time | build it before the loop |
queue.pop(0) / insert(0, x) on a list |
list.pop(0): 0.78 s for 100,000 |
every item shifts | collections.deque |
| optimising a guess | no faster | it wasn't the slow part | profile first |
| timing one tiny run | different every time | noise | timeit with number= |
| optimising before it works | fast wrong answers | correctness first | tests first (episode 29) |
The speed-up recipe
- Make it correct, with tests.
- Measure: is it actually too slow?
- Profile: find the top function.
- Fix its Big-O: set/dict lookups, no hidden loops,
dequefor queues, sort once instead of searching repeatedly. - Then shrink constants: built-ins, comprehensions, fewer function calls in hot loops.
- Waiting? Threads or async (episodes 31-32). Heavy calculation on every core? Processes.
Mini project: speed up Raju's nightly report
Slow version: 50,000 orders (phone, item, amount), 20,000 customers in a list, a hand-written counter, and a list used as a queue.
import random, time
random.seed(1)
MENU = ["chai", "samosa", "toast", "lassi", "poha", "vada pav", "coffee"]
customers = [9_000_000_000 + i * 7 for i in range(20_000)]
orders = [(9_000_000_000 + random.randrange(0, 300_000), random.choice(MENU), random.randint(10, 200))
for _ in range(50_000)]
def regulars(orders, customers):
return [o for o in orders if o[0] in customers]
def item_counts(orders):
counts = {}
for _, item, _ in orders:
if item in counts:
counts[item] += 1
else:
counts[item] = 1
return counts
def top5(orders):
spend = sorted(orders, key=lambda o: o[2], reverse=True)
return spend[:5]
def serve(orders):
queue = list(orders)
served = 0
while queue:
queue.pop(0)
served += 1
return served
def report():
r = regulars(orders, customers)
c = item_counts(orders)
t = top5(orders)
s = serve(orders)
return len(r), sorted(c.items()), [o[2] for o in t], s
start = time.perf_counter()
print(report())
print(f"took {time.perf_counter() - start:.2f} s")
Output:
(3257, [('chai', 7159), ('coffee', 7062), ('lassi', 7310), ('poha', 7117), ('samosa', 7224), ('toast', 7143), ('vada pav', 6985)], [200, 200, 200, 200, 200], 50000)
took 5.56 s
Profile (python3 -m cProfile -s tottime report_slow.py), top lines:
ncalls tottime percall cumtime percall filename:lineno(function)
1 5.046 5.046 5.046 5.046 report_slow.py:9(regulars)
50005 0.187 0.000 0.187 0.000 {method 'pop' of 'list' objects}
Solution: the fast version
from collections import Counter, deque
def regulars(orders, customers):
known = set(customers) # O(1) lookups
return [o for o in orders if o[0] in known]
def item_counts(orders):
return Counter(item for _, item, _ in orders)
def top5(orders):
return sorted(orders, key=lambda o: o[2], reverse=True)[:5]
def serve(orders):
queue = deque(orders)
served = 0
while queue:
queue.popleft()
served += 1
return served
Output (identical report):
(3257, [('chai', 7159), ('coffee', 7062), ('lassi', 7310), ('poha', 7117), ('samosa', 7224), ('toast', 7143), ('vada pav', 6985)], [200, 200, 200, 200, 200], 50000)
took 0.01 s
From about 5.6 s to 0.01 s, and the report line is exactly the same (check it with a test: assert fast_report() == slow_report()). heapq.nlargest(5, orders, key=lambda o: o[2]) would get the top 5 in O(n) instead of sorting everything.
Practice
1. Time in on a list vs a set of 1,000,000 numbers.
Solution
import timeit
items = list(range(1_000_000))
as_set = set(items)
print("list:", round(timeit.timeit(lambda: 999_999 in items, number=100), 3), "s for 100 lookups")
print("set: ", round(timeit.timeit(lambda: 999_999 in as_set, number=100), 6), "s for 100 lookups")
Output (one run):
list: 0.536 s for 100 lookups
set: 7e-06 s for 100 lookups
7e-06 is scientific notation for 0.000007 seconds.
2. What is the Big-O of each? (a) max(lst) (b) d["chai"] (c) sorted(lst) (d) for x in a: for y in a: ...
Answer
(a) O(n) (b) O(1) (c) O(n log n) (d) O(n²)
3. Write has_duplicate(items) in O(n).
Solution
def has_duplicate(items):
return len(set(items)) != len(items)
def has_duplicate_early(items):
seen = set()
for x in items:
if x in seen:
return True
seen.add(x)
return False
print(has_duplicate([4, 8, 15, 16, 23, 42]))
print(has_duplicate([4, 8, 15, 8]))
print(has_duplicate_early([4, 8, 15, 8]))
Output:
False
True
True
The second version stops as soon as it finds a duplicate.
4. Profile one of your own older programs with python3 -m cProfile -s tottime yourfile.py. Which function is on top?
Hint
Look at tottime first. If a built-in method like {method 'pop' of 'list' objects} or {method 'index' of 'list' objects} is near the top, a hidden O(n) loop is probably the cause.
Quick quiz
def has_duplicate(items):
for i in range(len(items)):
for j in range(i + 1, len(items)):
if items[i] == items[j]:
return True
return False
What is its Big-O? A. O(1) B. O(log n) C. O(n) D. O(n²)
Answer
D. A loop inside a loop over the same list: about n²/2 comparisons, and Big-O drops the ½. The O(n) version: len(set(items)) != len(items).
Interview questions
- What is Big-O notation? A way to describe how an algorithm's running time (or memory) grows with input size n, keeping the dominant term and ignoring constants.
- Why is
x in listO(n) butx in setO(1)? A list must compare items one by one; a set hashesxand jumps to its slot (O(1) on average; many hash collisions can make it worse). - Time complexity of
sorted()? O(n log n) (Timsort); O(n) when the data is already sorted. list.pop()vslist.pop(0)?pop()removes the last item, O(1);pop(0)shifts every item, O(n). Usecollections.dequefor queues.tottimevscumtimein cProfile?tottimeexcludes time in sub-calls;cumtimeincludes it.- Why are built-ins faster than an equivalent Python loop? They run in C, avoiding the interpreter's per-step overhead: same Big-O, smaller constant.
- What is space complexity? How much extra memory an algorithm needs as n grows, e.g. building a set of n items is O(n) space.
- When should you optimise? After the code is correct and measured to be too slow, starting with what the profiler shows.
Glossary
| Term | Meaning |
|---|---|
| performance | how much time and memory a program uses |
time.perf_counter() |
a precise stopwatch for timing code |
timeit |
runs code many times and reports the total time |
| benchmark | a repeatable timing measurement |
| n | the size of the input |
| Big-O notation | how the number of steps grows with n |
| time complexity | Big-O of running time |
| space complexity | Big-O of extra memory |
| O(1) constant | same work for any n |
| O(log n) logarithmic | work grows by one step each time n doubles |
| O(n) linear | double n, double the work |
| O(n log n) | the cost of good sorting |
| O(n²) quadratic | double n, four times the work |
| worst case | the most steps for any input of size n |
| constant factor | the fixed multiplier Big-O ignores (why built-ins win) |
| binary search | repeatedly halving sorted data to find a value |
| hash | a number computed from a value, used to find it in a set or dict |
| profiler | a tool that measures time spent in each function |
| cProfile / pstats | Python's built-in profiler / its report module |
ncalls, tottime, cumtime |
number of calls, time inside, time including sub-calls |
| built-in | a function that comes with Python, implemented in C (sum, max, sorted) |
collections.Counter |
a dict that counts things |
collections.deque |
a double-ended queue: O(1) add/remove at both ends |
| hidden loop | an operation that loops internally (in list, pop(0), index) |
Summary
- Don't guess: measure with
perf_counterandtimeit, and watch how the time grows when n doubles. - Big-O names that growth: O(1), O(log n), O(n), O(n log n), O(n²). Doubling n → 4× time means O(n²).
inon a list is O(n); on a set or dict it's O(1). One word turned Raju's O(n²) report into O(n).- cProfile shows which function to fix; fix its Big-O first.
- Built-ins and
collections(Counter,deque) are fast; never uselist.pop(0)as a queue. - Next episode: the master section begins with data structures: Raju's app needs an undo button, and you'll invent the stack and the queue.