Master Complexity Cheatsheet

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 list / dict / set / deque / heapq 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 n can be under a typical time limit.

Common Python operations

Operation	list	dict	set	deque	heapq
Index / key access 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)$ (heappush)
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)$ (heappop, smallest only)
Insert / delete at arbitrary index	$O(n)$	$O(1)$ avg (del d[k])	$O(1)$ avg	$O(n)$	not supported directly
Membership test 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])
Sort (sorted(...), .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) from scratch	—	—	—	—	Building via heapify is $O(n)$

The two list gotchas everyone hits

list.insert(0, x) and list.pop(0) both shift every remaining element down one slot — $O(n)$, not $O(1)$. If you need fast operations at both ends, reach for collections.deque instead; it’s $O(1)$ at both ends by design.

Sorting algorithms

Algorithm	Best	Average	Worst	Space	Stable?	Notes
Timsort (Python’s sorted/.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	k = range of key values; useless when k >> n
Radix Sort	$O(d(n + k))$	$O(d(n + k))$	$O(d(n + k))$	$O(n + k)$	Yes	d = 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_bound / upper_bound (bisect)	$O(\log n)$	$O(1)$	Sorted array
Binary search on the answer	$O(f(n) \log(\text{range}))$	Depends on feasible()	Monotonic feasibility
Hash-based lookup (dict/set)	$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 list	$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 (list as stack)	$O(n)$	$O(n)$	$O(1)$ (append)	$O(1)$ (pop)	$O(n)$	LIFO — both ops at the same end
Queue (collections.deque)	$O(n)$	$O(n)$	$O(1)$ (append)	$O(1)$ (popleft)	$O(n)$	FIFO — never use list.pop(0) here
Hash table (dict/set)	—	$O(1)$ avg, $O(n)$ worst	$O(1)$ avg	$O(1)$ avg	$O(n)$	Worst case needs adversarial hash collisions
Binary heap (heapq)	$O(1)$ (min only)	$O(n)$	$O(\log n)$	$O(\log n)$ (min)	$O(n)$	heapify 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})$	L = 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))$ find	$O(\alpha(n))$ union	—	$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

Picking a shortest-path algorithm

Unweighted -> BFS. Non-negative weights -> Dijkstra. Negative weights (no negative cycle) -> Bellman-Ford. Need every pair’s distance on a small graph -> Floyd-Warshall. Reach for the cheapest algorithm that satisfies your graph’s actual constraints — Floyd-Warshall’s $O(V^3)$ becomes infeasible well before Dijkstra’s $O((V + E) \log V)$ does.

The Big-O growth hierarchy

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

$$O(1) < O(\log n) < O(\sqrt{n}) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$

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

sketch Where each complexity crosses the one-second budget p5.js Pause Restart

Log-log axes: the horizontal axis is n from 1 to 10^9, the vertical is operation count from 1 to 10^18. The dashed line is the 10^8 budget from the table above. What matters is not the slope of any curve but where it crosses that line -- that crossing IS the maximum n the complexity can handle. Every crossing is solved on the fly by bisection, not read from a table.

Max n 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 n for each complexity class:

Complexity	Comfortable max n
$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)

Read the constraints backward

Given a time limit and a constraint like $n \le 10^5$, work the table in reverse: an $O(n^2)$ solution ($10^{10}$ operations) is almost certainly too slow, while $O(n \log n)$ ($\approx 1.7 \times 10^6$ operations) has room to spare. Constraints are a hint dropped by the problem setter about which complexity class they expect — always check them before writing a single line of code.

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.

pch.exerciseTag pch.exerciseTitle

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 n and a time limit, use the “max n 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).

Read the constraint, name the intended complexity

pch.exerciseTag pch.exerciseTitle

sketch Read the constraint, name the complexity p5.js Pause Restart

The constraint in the problem statement tells you the intended complexity, and this is the arithmetic that turns one into the other. n sweeps upward; for each complexity the bar shows the operation count against the 10^8 budget, and a class flips from green to red the moment it no longer fits. The rightmost class still green is the answer to give. Counts are computed live, so n = 2000 shows exactly the 4,000,000 the page states for O(n^2).

Count the operations, not the vibes

pch.exerciseTag pch.exerciseTitle

Complexity

The one table this whole page exists to support — what fits in about one second, at roughly $10^8$ simple operations:

Max n	Largest complexity that fits	Typical approach
<= 12	$O(n!)$	permutations, brute-force TSP
<= 25	$O(2^n)$	subsets, bitmask DP
<= 500	$O(n^3)$	Floyd-Warshall, interval DP
<= 5,000	$O(n^2)$	pairwise DP, LCS, edit distance
<= 10^5-10^6	$O(n \log n)$	sorting, heaps, segment trees, binary search on the answer
<= 10^7	$O(n)$	one pass, sliding window, prefix sums
>= 10^9	$O(\log n)$ / $O(1)$	binary search on the answer, closed form, digit DP

Two adjustments that matter in practice:

• Python’s constant factor is roughly 10-100x C++. Shift the table down about one order of magnitude for pure-Python loops — $10^7$ simple operations per second is a safer working figure than $10^8$. Work pushed into C (sort, sum, bytes, set operations, NumPy) does not pay that tax.
• Read the bound’s variable. “Binary search on the answer” is $O(n \log R)$ where $R$ is the value range, not n; a pseudo-polynomial DP like knapsack is $O(nW)$ in the capacity. Quoting either as a function of n alone is the usual mistake, and it is what makes a solution that looks fine time out.

Interview follow-ups

They ask	What they’re checking	The answer
“The constraint is n <= 20. What does that tell you?”	Reading constraints as hints	That exponential in n is expected — $2^{20}$ is about a million. A bound that small is almost always pointing at a bitmask or a full enumeration
“What is the complexity of list.insert(0, x)?”	Whether you know the data model	$O(n)$ — every element shifts. That is why a queue uses collections.deque, where both ends are $O(1)$
“in on a list versus a set?”	The most common Python performance bug	$O(n)$ versus $O(1)$ average. A membership test inside a loop turns an $O(n)$ algorithm into $O(n^2)$ without changing a line of the logic
“Amortised versus worst case?”	Precision	A list.append is $O(1)$ amortised and $O(n)$ on the resize that copies. Over n appends the total is $O(n)$, so amortised is the honest figure to quote for a loop
“Your solution is $O(n \log n)$ but times out”	Diagnosing beyond the class	Either the constant is the problem — Python-level loops, per-iteration allocation, string concatenation in a loop — or the bound’s variable is not what you assumed. Check both before rewriting the algorithm
“Space complexity of your recursion?”	The invisible cost	$O(h)$ stack frames, which is $O(n)$ on a degenerate input and invisible in the source. It is also why CPython’s ~1000-frame limit turns some correct solutions into crashes
“Sorting is $O(n \log n)$ — can you ever beat it?”	Knowing the model	Only by leaving the comparison model: counting or radix sort is $O(n + k)$ for small integer keys. The $\Omega(n \log n)$ bound applies to comparison sorts specifically
“Which of these bounds do people quote wrongly?”	Judgement	Pseudo-polynomial ones — knapsack’s $O(nW)$ and digit DP’s — because they are polynomial in a value rather than an input length. Naive Fibonacci is $O(\phi^n)$, not $O(2^n)$

LeetCode problem set

Problems whose intended solution is decided by a complexity budget rather than a trick. For each, work out the target complexity from the constraints before looking at the tags.

29 problems

8 easy16 medium5 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○1Two SumeasyNeetCode 150Blind 75LeetCode Top Interview 150amazongooglemetamicrosoftapplebloomberg
• ○121Best Time to Buy and Sell StockeasyNeetCode 150Blind 75LeetCode Top Interview 150amazonmetamicrosoftbloomberg
• ○21Merge Two Sorted ListseasyNeetCode 150Blind 75LeetCode Top Interview 150amazonmicrosoftapplebloomberg
• ○217Contains DuplicateeasyNeetCode 150Blind 75amazonapplemicrosoft
• ○35Search Insert PositioneasyLeetCode Top Interview 150
• ○169Majority ElementeasyLeetCode Top Interview 150
• ○704Binary SearcheasyNeetCode 150
• ○1046Last Stone WeighteasyNeetCode 150
• ○33Search in Rotated Sorted ArraymediumNeetCode 150Blind 75LeetCode Top Interview 150amazonmetamicrosoftbloomberg
• ○49Group AnagramsmediumNeetCode 150Blind 75LeetCode Top Interview 150amazonmetauberbloomberg
• ○75Sort Colorsmediumamazonmicrosoftmeta
• ○347Top K Frequent ElementsmediumNeetCode 150Blind 75amazonmetauberbytedance
• ○621Task SchedulermediumNeetCode 150metaamazonuber
• ○875Koko Eating BananasmediumNeetCode 150googleamazonbytedance
• ○34Find First and Last Position of Element in Sorted ArraymediumLeetCode Top Interview 150
• ○36Valid SudokumediumNeetCode 150LeetCode Top Interview 150
• ○189Rotate ArraymediumLeetCode Top Interview 150
• ○215Kth Largest Element in an ArraymediumNeetCode 150LeetCode Top Interview 150
• ○274H-IndexmediumLeetCode Top Interview 150
• ○763Partition LabelsmediumNeetCode 150
• ○846Hand of StraightsmediumNeetCode 150
• ○912Sort an Arraymedium
• ○981Time Based Key-Value StoremediumNeetCode 150
• ○2013Detect SquaresmediumNeetCode 150
• ○23Merge k Sorted ListshardNeetCode 150Blind 75LeetCode Top Interview 150
• ○135CandyhardLeetCode Top Interview 150
• ○315Count of Smaller Numbers After Selfhard
• ○493Reverse Pairshard
• ○1851Minimum Interval to Include Each QueryhardNeetCode 150

Recall card

• The budget — about $10^8$ simple operations per second, and an order of magnitude fewer in pure Python. Do this arithmetic before choosing an approach.
• Constraint to complexity — n <= 12: $O(n!)$ · <= 25: $O(2^n)$ · <= 500: $O(n^3)$ · <= 5000: $O(n^2)$ · <= 10^6: $O(n \log n)$ · <= 10^7: $O(n)$ · beyond: $O(\log n)$ or a formula.
• Python data model — list.insert(0, ...) and list.pop(0) are $O(n)$; deque is $O(1)$ at both ends. x in list is $O(n)$, x in set is $O(1)$ — the most common accidental $O(n^2)$.
• append is $O(1)$ amortised, $O(n)$ on the resize. Quote the amortised figure for a loop.
• Recursion costs $O(h)$ space and dies at ~1000 frames in CPython.
• Read the bound’s variable — $O(nW)$ and $O(n \log R)$ are polynomial in a value, not a length. That is what makes a “fine” solution time out.
• Beating $O(n \log n)$ requires leaving the comparison model: counting or radix sort.

Recap

• Python’s built-in containers hide real complexity costs — list.pop(0) and list.insert(0, x) are $O(n)$, not $O(1)$; use deque 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()/.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.