What each operation costs, in one place: Python's built-in containers, the classic data structures,
sorting, graph algorithms, dynamic programming, and vectorized NumPy and pandas. Use it to choose a structure
before you write code, and to explain why slow code is slow.
Read Big-O, average vs worst case, and amortized cost correctly
Know the cost of every common list, dict, set, deque, heapq, str, and bisect operation
Compare sorting, graph, and DP algorithms by time, space, and stability
Choose the right structure for a job with a decision flowchart
Growth rates
Big-O describes how cost grows with input size n, ignoring constant factors. Below,
n is the container size, k is the size of the argument or result, V/E
are vertices and edges. "Amortized O(1)" means an occasional expensive step averages out to constant per
operation. "Average" for hash tables assumes a decent hash function; the worst case (all keys colliding) is
O(n).
* amortized. L = key length; α = inverse Ackermann (at most 4 for any practical n); k = number of hash functions.
Sorting algorithms
Algorithm
Best
Average
Worst
Extra space
Stable?
When to use
Bubble sort
O(n)
O(n²)
O(n²)
O(1)
Yes
Teaching only
Selection sort
O(n²)
O(n²)
O(n²)
O(1)
No
Minimizes writes
Insertion sort
O(n)
O(n²)
O(n²)
O(1)
Yes
Tiny or nearly sorted inputs
Shell sort
O(n log n)
gap-dependent (~n1.3)
O(n1.5) or better
O(1)
No
Embedded, no recursion
Merge sort
O(n log n)
O(n log n)
O(n log n)
O(n)
Yes
Linked lists, external sorting
Quicksort
O(n log n)
O(n log n)
O(n²)
O(log n) stack
No
In-place general purpose (random pivot)
Heapsort
O(n log n)
O(n log n)
O(n log n)
O(1)
No
Guaranteed bound, constant space
Counting sort
O(n + k)
O(n + k)
O(n + k)
O(n + k)
Yes
Small integer range k
Radix sort (LSD)
O(d(n + b))
O(d(n + b))
O(d(n + b))
O(n + b)
Yes
Fixed-width keys (d digits, base b)
Bucket sort
O(n + k)
O(n + k)
O(n²)
O(n + k)
Yes*
Uniformly distributed floats
Python sorted / list.sort (Timsort with Powersort merging)
O(n)
O(n log n)
O(n log n)
O(n)
Yes
Always, in real Python code
* if the per-bucket sort is stable. A sort is stable when equal keys keep their original order, which
lets you sort by several keys in passes. Comparison sorts cannot beat O(n log n) in the worst case. Watch them
race in M29 Sorting:
NumPy and pandas operations have the same Big-O as the equivalent Python loop, often O(n), but the loop runs
in compiled code over contiguous memory, so the constant is 10–100× smaller. The rule: push loops into the
library.
Operation
Cost
Notes
a + b, a * 2, np.sqrt(a), comparisons
O(n), vectorized
Broadcasting avoids copies of the smaller operand
a.sum(), a.mean(), a.max()
O(n)
Pairwise summation for floats
a[i], basic slice a[2:10]
O(1)
A slice is a view: no copy
Boolean mask a[a > 0], fancy index a[[1, 5]]
O(n) / O(k)
Always a copy
np.append, np.concatenate in a loop
O(n²) total
Preallocate, or collect in a list then concatenate once
flowchart TD
Q{"What do you mostly do?"} --> A["Look up by key"]
Q --> B["Keep things in order"]
Q --> C["Take the smallest or largest next"]
Q --> D["Add and remove at the ends"]
Q --> E["Test membership or de-duplicate"]
Q --> F["Heavy numeric math"]
A --> A1{"Need the keys sorted?"}
A1 -- no --> A2["dict O(1)"]
A1 -- yes --> A3["sorted list + bisect, or a balanced tree"]
B --> B1{"Mostly append and index?"}
B1 -- yes --> B2["list"]
B1 -- "insert in the middle often" --> B3["bisect.insort for small n, else a balanced tree"]
C --> C1["heapq O(log n)"]
D --> D1{"Only one end?"}
D1 -- "yes, LIFO" --> D2["list as a stack"]
D1 -- "both ends or FIFO" --> D3["collections.deque"]
E --> E1{"Need counts?"}
E1 -- no --> E2["set O(1)"]
E1 -- yes --> E3["Counter"]
F --> F1["NumPy array or pandas / Polars"]