SyntaxPilot
Courses/Python/Lesson 33
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python · Lesson 33 of 40

Performance: Big-O, profiling, built-ins

queued

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): runs func N 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 + 5 steps is O(n). Big-O is about growth, not exact counts.
  • Keep the biggest term: n² + n is O(n²).
  • Hidden loops count: x in a_list, lst.index(x), lst.remove(x), lst.pop(0) and lst.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 where x is, 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 called stats.
  • pstats.Stats("stats").get_stats_profile() (Python 3.9+) gives a profile whose func_profiles maps each function name to its numbers: ncalls, tottime, cumtime, file_name, line_number.
  • We sort by tottime and print the top three. find_known takes 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 what func returns (episode 17); reverse=True for highest first. max/min take a key too.
  • 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

  1. Make it correct, with tests.
  2. Measure: is it actually too slow?
  3. Profile: find the top function.
  4. Fix its Big-O: set/dict lookups, no hidden loops, deque for queues, sort once instead of searching repeatedly.
  5. Then shrink constants: built-ins, comprehensions, fewer function calls in hot loops.
  6. 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

  1. 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.
  2. Why is x in list O(n) but x in set O(1)? A list must compare items one by one; a set hashes x and jumps to its slot (O(1) on average; many hash collisions can make it worse).
  3. Time complexity of sorted()? O(n log n) (Timsort); O(n) when the data is already sorted.
  4. list.pop() vs list.pop(0)? pop() removes the last item, O(1); pop(0) shifts every item, O(n). Use collections.deque for queues.
  5. tottime vs cumtime in cProfile? tottime excludes time in sub-calls; cumtime includes it.
  6. 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.
  7. 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.
  8. 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_counter and timeit, 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²).
  • in on 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 use list.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.