Complexity is the one thing you’re expected to know cold, without looking it up mid-interview or mid-contest. This page is the single-place reference: every operation, data structure, and algorithm from this track, with its time and space complexity side by side. Treat it as a lookup table, not a lesson — if a row doesn’t make sense, the phase that taught it is linked from context in earlier pages.

What you’ll learn

• The real complexity of every common listlist / dictdict / setset / dequedeque / heapqheapq operation — including the ones that silently cost $O(n)$.
• Every sorting and searching algorithm from Phase 4, side by side.
• Every data structure’s core operations, from arrays to segment trees, Fenwick trees, and DSU.
• The graph algorithm family — BFS, DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, MST, and topological sort.
• The Big-O growth hierarchy, and a rule of thumb for how large nn can be under a typical time limit.

Common Python operations

Operation	listlist	dictdict	setset	dequedeque	heapqheapq
Index / key access x[i]x[i]	$O(1)$	$O(1)$ avg	—	$O(n)$	—
Append / add	$O(1)$ amortized	$O(1)$ avg	$O(1)$ avg	$O(1)$	$O(\log n)$ (heappushheappush)
Append/insert at front	$O(n)$	—	—	$O(1)$	—
Pop from end	$O(1)$	—	—	$O(1)$	—
Pop from front	$O(n)$	—	—	$O(1)$	$O(\log n)$ (heappopheappop, smallest only)
Insert / delete at arbitrary index	$O(n)$	$O(1)$ avg (del d[k]del d[k])	$O(1)$ avg	$O(n)$	not supported directly
Membership test x in ...x in ...	$O(n)$	$O(1)$ avg	$O(1)$ avg	$O(n)$	$O(n)$
Search for min/max	$O(n)$	$O(n)$	$O(n)$	$O(n)$	$O(1)$ (min only, heap[0]heap[0])
Sort (sorted(...)sorted(...), .sort().sort())	$O(n \log n)$	$O(n \log n)$ on items	$O(n \log n)$ on items	$O(n \log n)$	$O(n \log n)$ (heapify + drain)
sorted(list)sorted(list) from scratch	—	—	—	—	Building via heapifyheapify is $O(n)$

Sorting algorithms

Algorithm	Best	Average	Worst	Space	Stable?	Notes
Timsort (Python’s sortedsorted/.sort().sort())	$O(n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	Yes	Adaptive — exploits existing runs of order
Merge Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	Yes	Guaranteed $O(n \log n)$, no worst-case cliff
Quick Sort	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$	No	Worst case needs an adversarial/sorted input plus a bad pivot rule
Heap Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	No	In-place, but poor cache locality in practice
Insertion Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Yes	Best-in-class for nearly-sorted or tiny arrays
Selection Sort	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	No	Always $O(n^2)$ comparisons, minimal writes
Bubble Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Yes	Teaching tool only — never the right production choice
Counting Sort	$O(n + k)$	$O(n + k)$	$O(n + k)$	$O(n + k)$	Yes	kk = range of key values; useless when kk >> nn
Radix Sort	$O(d(n + k))$	$O(d(n + k))$	$O(d(n + k))$	$O(n + k)$	Yes	dd = number of digits/passes
Bucket Sort	$O(n + k)$	$O(n + k)$	$O(n^2)$	$O(n)$	Yes (with a stable inner sort)	Needs a roughly-uniform input distribution

Searching

Technique	Time	Space	Requires
Linear search	$O(n)$	$O(1)$	Nothing
Binary search (exact match)	$O(\log n)$	$O(1)$	Sorted array
lower_boundlower_bound / upper_boundupper_bound (bisectbisect)	$O(\log n)$	$O(1)$	Sorted array
Binary search on the answer	$O(f(n) \log(\text{range}))$	Depends on feasible()feasible()	Monotonic feasibility
Hash-based lookup (dictdict/setset)	$O(1)$ average, $O(n)$ worst	$O(n)$	Hashable keys
Two pointers / sliding window	$O(n)$	$O(1)$	Sorted or monotonic structure

Core data structures

Structure	Access	Search	Insert	Delete	Space	Notes
Array / Python listlist	$O(1)$	$O(n)$	$O(n)$ worst (end: $O(1)$ amortized)	$O(n)$	$O(n)$	Contiguous, cache-friendly
Singly/doubly linked list	$O(n)$	$O(n)$	$O(1)$ at a known node	$O(1)$ at a known node	$O(n)$	No random access; cheap splicing
Stack (listlist as stack)	$O(n)$	$O(n)$	$O(1)$ (appendappend)	$O(1)$ (poppop)	$O(n)$	LIFO — both ops at the same end
Queue (collections.dequecollections.deque)	$O(n)$	$O(n)$	$O(1)$ (appendappend)	$O(1)$ (popleftpopleft)	$O(n)$	FIFO — never use list.pop(0)list.pop(0) here
Hash table (dictdict/setset)	—	$O(1)$ avg, $O(n)$ worst	$O(1)$ avg	$O(1)$ avg	$O(n)$	Worst case needs adversarial hash collisions
Binary heap (heapqheapq)	$O(1)$ (min only)	$O(n)$	$O(\log n)$	$O(\log n)$ (min)	$O(n)$	heapifyheapify builds from scratch in $O(n)$
Binary Search Tree (unbalanced)	$O(n)$ worst	$O(n)$ worst	$O(n)$ worst	$O(n)$ worst	$O(n)$	Degenerates to a linked list on sorted input
Balanced BST (AVL / Red-Black)	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$	Guarantees hold even on adversarial input
Trie	$O(L)$	$O(L)$	$O(L)$	$O(L)$	$O(\text{total chars})$	LL = length of the key/word
Segment Tree	$O(\log n)$ query/update	—	$O(\log n)$ update	—	$O(n)$	$O(n)$ build; lazy propagation keeps range updates $O(\log n)$
Fenwick Tree (BIT)	$O(\log n)$ query	—	$O(\log n)$ update	—	$O(n)$	Simpler and faster in practice than a segment tree for prefix sums
Disjoint Set Union (DSU)	—	$O(\alpha(n))$ findfind	$O(\alpha(n))$ unionunion	—	$O(n)$	With path compression + union by rank/size; $\alpha$ is the inverse Ackermann function — effectively constant

Graph algorithms

Algorithm	Time	Space	Answers
BFS	$O(V + E)$	$O(V)$	Shortest path in an unweighted graph, level order, multi-source distance
DFS	$O(V + E)$	$O(V)$	Reachability, cycle detection, topological order, connected components
Topological sort (Kahn’s or DFS-based)	$O(V + E)$	$O(V)$	A valid linear order of a DAG
Dijkstra (binary heap)	$O((V + E) \log V)$	$O(V)$	Shortest path, non-negative weights only
Bellman-Ford	$O(V \cdot E)$	$O(V)$	Shortest path with negative weights; also detects negative cycles
Floyd-Warshall	$O(V^3)$	$O(V^2)$	All-pairs shortest paths, works with negative weights (no negative cycles)
Prim’s MST (binary heap)	$O(E \log V)$	$O(V)$	Minimum spanning tree, dense-ish graphs
Kruskal’s MST (with DSU)	$O(E \log E)$	$O(V)$	Minimum spanning tree, sparse graphs / edge lists

The Big-O growth hierarchy

From fastest-growing-slowly to fastest-growing-explosively:

Complexity	Name	Feels like
$O(1)$	Constant	A dict lookup, an array index
$O(\log n)$	Logarithmic	Binary search, balanced BST operations
$O(\sqrt{n})$	Root	Trial-division primality check, sparse tables’ build-adjacent factor
$O(n)$	Linear	A single pass — linear search, array sum
$O(n \log n)$	Linearithmic	Comparison-based sorting, most divide-and-conquer
$O(n^2)$	Quadratic	Nested loops over the same input — naive pair comparisons
$O(n^3)$	Cubic	Triple-nested loops — Floyd-Warshall, naive matrix multiply
$O(2^n)$	Exponential	Enumerating every subset, unmemoized exponential recursion
$O(n!)$	Factorial	Enumerating every permutation

Max nn per time limit — a rule of thumb

Contest judges typically allow roughly $10^8$-$10^9$ simple operations per second in Python (often with a looser limit than C++ for exactly this reason). Working backward from a 1-2 second limit gives a rough ceiling on nn for each complexity class:

Complexity	Comfortable max nn
$O(n!)$	$n \le 10$-ish
$O(2^n)$	$n \le 20$-25
$O(n^3)$	$n \le 300$-500
$O(n^2)$	$n \le 5{,}000$-10,000
$O(n \log n)$	$n \le 10^6$-$10^7$
$O(n)$	$n \le 10^7$-$10^8$
$O(\log n)$ / $O(1)$	$n$ up to $10^{18}$ (the input size barely matters)

Practice

Self-check — reading a constraint. Given $n \le 2000$ and a 1-second limit, complete the comparison that decides whether an $O(n^2)$ solution fits comfortably.

How to use this cheatsheet

• Treat it as a lookup, not reading material — bookmark it and come back mid-problem when you need to double-check a complexity before committing to an approach.
• When a problem gives you nn and a time limit, use the “max nn per time limit” table to shortlist which complexity classes are even in the running before you design an algorithm.
• When two data structures both “work,” pick the one whose row here has the better guarantee for the operation your problem calls the most (e.g. a Fenwick tree over a segment tree when you only need prefix sums, not range updates).

Recap

• Python’s built-in containers hide real complexity costs — list.pop(0)list.pop(0) and list.insert(0, x)list.insert(0, x) are $O(n)$, not $O(1)$; use dequedeque when you need fast operations at both ends.
• Timsort’s $O(n \log n)$ worst case and $O(n)$ best case (on already-sorted runs) is why sorted()sorted()/.sort().sort() is almost always the right call over a hand-rolled sort.
• Balanced BSTs, Fenwick trees, and segment trees all trade a bit of extra bookkeeping for a guaranteed $O(\log n)$ where a naive structure would degrade to $O(n)$ on adversarial input.
• Shortest-path algorithm choice is driven entirely by what the graph allows: unweighted -> BFS, non-negative weights -> Dijkstra, negative weights -> Bellman-Ford, all-pairs on a small graph -> Floyd-Warshall.
• The Big-O hierarchy plus a rough “operations per second” budget is enough to sanity-check almost any algorithm choice before you write a line of code.

Next: Phase 10 — Interview & Contest Strategy, where these templates and complexity guarantees get applied under real time pressure: how to plan an approach, communicate it, and choose the right tool fast when the clock is running.