beginnerintermediateadvanced

Python · Performance

Fundamentals

Concepts: 3

Big-O and complexity as the vocabulary for describing growth, the roadmap's own list-vs-set example as the concrete payoff of choosing the right data structure, and the six distinct root causes a slow application can actually have.

This section

A Simple & Effective Way To Improve Python Class PerformanceArjanCodes

The vocabulary of cost

How to describe and measure what makes code slow, before trying to fix it.

Big-O, time complexity, and space complexity

coreintermediate

Big-O describes how an algorithm's cost grows as input size grows, ignoring constant factors. Time complexity measures growth in operations; space complexity measures growth in memory — both are about the SHAPE of growth.

Think of it as

Big-O answers "what happens if the input gets 10x bigger?" — not "how many milliseconds does this take right now." O(n) means 10x the input costs roughly 10x the work; O(n²) means 10x the input costs roughly 100x the work — the shape of the curve, not today's exact number.

python

# O(1)      dict[key], set membership
# O(n)       for item in items: ...
# O(n log n) sorted(items)
# O(n^2)     nested loop over the same collection

What we're doing: Measure O(n) vs O(n²) duplicate-detection on the same real input and see the growth-rate difference directly.

complexity_comparison.pypython

import time

def has_duplicate_on(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

def has_duplicate_on2(items):
    for i, a in enumerate(items):
        for b in items[i + 1:]:
            if a == b:
                return True
    return False

items = list(range(5000)) + [4999]  # duplicate at the very end -- worst case

start = time.perf_counter()
has_duplicate_on(items)
t1 = time.perf_counter() - start

start = time.perf_counter()
has_duplicate_on2(items)
t2 = time.perf_counter() - start

print(f"O(n):  {t1:.5f}s")
print(f"O(n^2): {t2:.5f}s")
print(f"n^2 version is {t2 / t1:.0f}x slower")

3: A set lookup (item in seen) is O(1) — this whole function is O(n): one pass, constant work per item.
11: The nested loop compares every pair — O(n²) work, even though it does the exact same logical job.

Output

O(n):  0.00056s
O(n^2): 0.32827s
n^2 version is 584x slower

Why this works: Both functions solve the exact same problem (find a duplicate) and return the same answer — but the O(n²) version compares every pair, so at 5,000 items it does roughly 12.5 million comparisons versus the O(n) version's 5,000. The exact multiplier varies run to run (measured 500x-900x across repeated runs, since the O(n) time is tiny and noisy) — but the gap stays in the hundreds-of-times range every time, which is Big-O's abstract growth rate made concrete.

Optimizing constant factors while the algorithm stays O(n²)

Wrong

python

def has_duplicate_faster_constant(items):
    # micro-optimized inner loop, STILL nested -- still O(n^2)
    n = len(items)
    for i in range(n):
        for j in range(i + 1, n):
            if items[i] == items[j]:
                return True
    return False

Better

python

def has_duplicate(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False   # O(n) -- the algorithm itself changed, not just its constants

What you see: A "faster" version still grinds to a halt on larger inputs, because micro-optimizing the inner loop only shrinks the constant factor — the O(n²) shape is unchanged.

Why: Big-O is about the SHAPE of growth. Shaving milliseconds off each comparison in an O(n²) algorithm still leaves it O(n²) — at large enough input, an unoptimized O(n) algorithm always eventually wins.

Growth rate vs. input size — where each shape lands

ExpensiveCheap

Small nLarge n

O(1): dict[key], set membership — flat, always
O(log n): binary search — grows very slowly
O(n): a single loop over n items
O(n log n): sorted(), list.sort()
O(n²): nested loop — measured 584x slower at n=5000

Common complexities, smallest to largest

Common complexities, smallest to largest
Notation	Name	Example
O(1)	Constant	dict[key], set membership, list.append()
O(log n)	Logarithmic	binary search, balanced tree lookup
O(n)	Linear	x in list, a single loop over n items
O(n log n)	Linearithmic	sorted(), list.sort()
O(n²)	Quadratic	a nested loop comparing every pair

Together

python

def has_duplicate_on(items):
    seen = set()
    for item in items:
        if item in seen:  # O(1)
            return True
        seen.add(item)
    return False  # overall: O(n)

def has_duplicate_on2(items):
    for i, a in enumerate(items):
        for b in items[i + 1:]:  # nested loop
            if a == b:
                return True
    return False  # overall: O(n^2)

Remember: Big-O describes how cost grows with input size, not today's runtime — O(n) eventually beats O(n²), however tuned.

Choosing the right data structure

coreintermediate

x in list checks every item one by one — O(n). x in set (or dict) hashes the value and jumps straight to it — O(1). For repeated membership testing, a set is often dramatically faster than a list, at the cost of losing order and duplicates.

Think of it as

A list is a row of unlabeled boxes — finding one means checking each box in order. A set is a filing cabinet with a hashed index — you compute where the item WOULD be and look directly there, no matter how many other items exist.

python

# O(n) -- checks every item
if x in my_list:
    ...

# O(1) average -- hashes x, jumps to it
if x in my_set:
    ...

What we're doing: Measure list vs. set membership testing on the exact same data, repeated 1,000 times each, and see the real gap.

list_vs_set.pypython

import timeit

t_list = timeit.timeit("x in lst", setup="lst = list(range(10000)); x = 9999", number=1000)
t_set = timeit.timeit("x in s", setup="s = set(range(10000)); x = 9999", number=1000)

print(f"list: {t_list:.5f}s")
print(f"set:  {t_set:.5f}s")
print(f"set is {t_list / t_set:.0f}x faster")

2: x = 9999 is the LAST item in a 10,000-item list — the worst case, since the list scan checks every earlier item first.
4: The same worst-case value in a set — the hash lookup jumps straight there regardless of position.

Output

list: 0.09500s
set:  0.00003s
set is 2969x faster

Why this works: The list version scans all 10,000 items (worst case, since x is last) on every one of the 1,000 repeated checks — 10 million comparisons total. The set version hashes x once per check regardless of collection size — the nearly 3000x gap is the direct, measured cost of O(n) vs O(1).

Using a list for repeated membership checks in a hot loop

Wrong

python

blocked_ids = [101, 205, 309, ...]  # a LIST, checked in a loop

for user in all_users:
    if user.id in blocked_ids:   # O(n) EVERY iteration
        skip(user)

Better

python

blocked_ids = {101, 205, 309, ...}  # a SET, converted ONCE

for user in all_users:
    if user.id in blocked_ids:   # O(1) every iteration
        skip(user)

What you see: A loop that checks membership against a list gets dramatically slower as either the list or the loop itself grows — O(n) work repeated n times is O(n²) overall.

Why: A list scan repeated inside another loop compounds — checking membership n times against an n-item list is O(n²) total work. Converting to a set once outside the loop turns each check into O(1), making the whole loop O(n) instead.

What you need decides the container

Key-value lookupNo key-value

Fast membershipOrder/duplicates matter

set: O(1) membership, no order, no duplicates
list: O(n) membership, order and duplicates preserved
dict: O(1) key lookup, associates a value
Counter: preserves counts AND gives fast lookup

Container choice by what you actually need

Container choice by what you actually need
Need	Use
Fast membership testing	set (or dict if you also need a value)
Order matters, duplicates OK	list
Key-value lookup	dict — O(1) average
Fixed-size unique items, need to add/remove	set

Together

python

valid_ids = {101, 205, 309}   # set -- fast membership
if user_id in valid_ids:      # O(1)
    ...

ordered_log = [101, 205, 101, 309]  # list -- order and duplicates matter

Remember: x in list is O(n); x in set/dict is O(1) average — convert to a set once if membership is checked more than a few times, especially inside a loop.

CPU, memory, I/O, network, database, and serialization bottlenecks

coreintermediate

A slow application has one of several root causes — CPU-bound, too much data in memory, waiting on disk, waiting on the network, a slow query, or converting data to/from JSON. Each needs a different fix.

Think of it as

A slow restaurant could be slow because the kitchen is understaffed (CPU), the pantry is disorganized (memory), deliveries are late (I/O/network), the supplier is slow (database), or repackaging every dish takes forever (serialization) — the fix for each is completely different, and guessing wrong wastes the effort.

python

# Diagnose FIRST, with a profiler (cProfile, py-spy) or by
# watching CPU usage -- do not guess which bottleneck it is.
python -m cProfile -s cumulative myapp.py

What we're doing: Contrast a genuinely CPU-bound function against a genuinely I/O-bound one, using cProfile to show where the time actually goes for each.

bottleneck_types.pypython

import time

def cpu_bound_work():
    total = 0
    for i in range(5_000_000):
        total += i * i
    return total

def io_bound_work():
    time.sleep(0.1)   # stands in for a real disk/network wait
    return "done"

start = time.perf_counter()
cpu_bound_work()
print(f"CPU-bound: {time.perf_counter() - start:.3f}s (spent computing)")

start = time.perf_counter()
io_bound_work()
print(f"I/O-bound: {time.perf_counter() - start:.3f}s (spent waiting)")

4: This loop genuinely keeps the CPU busy the whole time — a profiler would show time spent inside this function's own code.
9: time.sleep stands in for a real wait (disk, network) — a profiler would show this as time in a system call, not computation.

Output

CPU-bound: 0.413s (spent computing)
I/O-bound: 0.100s (spent waiting)

Why this works: Both took real wall-clock time, but for entirely different reasons — the CPU-bound function occupied a core computing for its whole duration; the I/O-bound function's time was almost entirely idle waiting. The fix for one (a faster algorithm, multiprocessing) does nothing for the other (which needs async I/O or threading instead).

Six root causes, six different fixes

CPU-bound

busy computing — better algorithm, multiprocessing

Memory-bound

too much held at once — GC pressure

I/O-bound

waiting on disk — async I/O, threading

Network-bound

waiting on a remote service

Database-bound

slow query, or N+1 round trips

Serialization

json.dumps/loads at scale

Adding more workers to fix what is actually an I/O bottleneck

Wrong

python

# app is slow -- assumed CPU-bound, added more worker PROCESSES
# but each worker just waits on the same slow database anyway
gunicorn --workers 16 myapp:app   # more CPU parallelism, wrong fix

Better

python

# profiled first -- found the app is I/O-bound (waiting on DB queries)
# fix: async I/O, connection pooling, or query optimization -- not more workers
gunicorn --workers 4 --worker-class uvicorn.workers.UvicornWorker myapp:app

What you see: Adding more CPU-bound worker processes does not meaningfully improve throughput, because every worker was already spending its time waiting on the database, not computing.

Why: More processes only helps a CPU-bound bottleneck, where more workers means more parallel computation. An I/O-bound bottleneck needs a different fix entirely (async I/O, pooling, faster queries) — throwing more processes at it just means more processes waiting on the same slow resource.

Bottleneck type, symptom, and typical fix

Bottleneck type, symptom, and typical fix
Bottleneck	Symptom	Typical fix
CPU-bound	High CPU usage, profiler shows time in Python code	Better algorithm, multiprocessing, a faster language extension
I/O-bound	Low CPU usage, process mostly waiting	Async I/O, or threading for concurrent waits
Database-bound	Slow query, or many small queries (N+1)	Add an index, batch queries, cache results
Serialization cost	Time spent in json.dumps/loads at scale	A faster serializer, or serialize less data

Together

python

# CPU-bound: heavy computation
def compute_hash(data):
    return hashlib.sha256(data).hexdigest()   # genuinely busy

# I/O-bound: waiting, not computing
def read_large_file(path):
    with open(path) as f:
        return f.read()   # waiting on disk

Remember: A slow app has a specific root cause — CPU, memory, I/O, network, database, or serialization — profile to find which.