beginnerintermediateadvanced

Python · Performance fundamentals

Performance fundamentals

Big-O, choosing the right data structure, and the six different reasons an application can actually be slow

Big-Othe SHAPE of growth, not today's exact runtime
list vs. setO(n) vs O(1) membership — a measured ~500-900x gap
Six bottleneck typesCPU, memory, I/O, network, database, serialization

1.Big-O, time complexity, and space complexity

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.

Key features

O(1): constant — cost does not grow with input size (dict/set lookup)
O(n): linear — cost grows proportionally with input size (scanning a list once)
O(n²): quadratic — cost grows with the square of input size (comparing every pair)
O(log n): logarithmic — cost grows very slowly as input grows (binary search)
Big-O describes the WORST case by convention, ignoring constants — O(2n) is just O(n)

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

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

Command

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

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

2.Choosing the right data structure

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.

Key features

list membership (x in list) is O(n) — worst case, every item gets compared
set and dict membership (x in a_set, key in a_dict) is O(1) on average — a hash lookup
Converting a list to a set once is worth it if membership is checked more than a few times
A set has no order and no duplicates — do not reach for one where either property matters
list is right for ordered data, indexing by position, or when duplicates matter

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

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

Command

python

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

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

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.

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

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.

Key features

CPU-bound: genuinely busy computing — a profiler shows time IN Python code, not waiting
Memory-bound: too much data held at once, causing slow allocation or GC pressure
I/O-bound: waiting on disk I/O — a profiler shows time in system calls, not compute
Network-bound: waiting on a remote service — often the largest cost in a web backend
Database-bound: a slow query (often a missing index) or too many round trips (N+1)
Serialization cost: converting data to/from JSON — easy to overlook, real at scale

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

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

Command

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

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

Spotted a mistake on this page? Tell us.

Read Sheet