Big-O Complexity Reference (1 page)

Common Time Complexities (fastest to slowest)

Notation	Name	Example	n=10^6 ops
O(1)	Constant	Hash lookup, array index	1
O(log n)	Logarithmic	Binary search	20
O(sqrt(n))	Square root	Trial division	1000
O(n)	Linear	Linear scan, counting sort	10^6
O(n log n)	Linearithmic	Merge sort, heap sort	2x10^7
O(n^2)	Quadratic	Nested loops, bubble sort	10^12 BAD
O(n^3)	Cubic	Floyd-Warshall, matrix mult	10^18 BAD
O(2^n)	Exponential	Subsets, brute force	heat death
O(n!)	Factorial	Permutations	heat death

Rule of thumb: ~10^8 simple operations per second in Python. For n=10^6, need O(n log n) or better.

n limit	Target complexity
n <= 10	O(n!) or O(2^n)
n <= 20	O(2^n)
n <= 25	O(2^(n/2))
n <= 100	O(n^3)
n <= 1000	O(n^2)
n <= 10^5	O(n log n)
n <= 10^6	O(n) or O(n log n)
n <= 10^8	O(n)
n > 10^8	O(log n) or O(1)

---

Python Built-in Operation Costs

list

Operation	Time
a[i], a[i]=x, len, append, pop()	O(1)
pop(i), insert(i,x), del a[i], x in a, index	O(n)
sort	O(n log n)
a[i:j], extend(k items)	O(j-i), O(k)
a + b	O(n+m)

dict / set

Operation	Average
get, set, del, in, add, remove	O(1)
union, intersection, difference	O(n+m), O(min), O(n)
iteration	O(n)

str

Operation	Time
s[i], len	O(1)
s + t, s[i:j], in, find, replace, split, join	O(n)
Danger: s += c in loop = O(n^2) total. Use ''.join(parts)

deque

Operation	Time
append, appendleft, pop, popleft	O(1)
a[i] (random access)	O(n)

---

Sorting Algorithm Comparison

Algorithm	Best	Average	Worst	Space	Stable	Notes
Timsort (Python)	O(n)	O(n log n)	O(n log n)	O(n)	Yes	Python's sorted()/list.sort()
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	Divide & conquer
Quick Sort	O(n log n)	O(n log n)	O(n^2)	O(log n)	No	Randomized pivot avoids worst
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No	In-place but not cache-friendly
Counting Sort	O(n+k)	O(n+k)	O(n+k)	O(k)	Yes	k = range of values
Radix Sort	O(d(n+k))	O(d(n+k))	O(d(n+k))	O(n+k)	Yes	d = digits, k = base
Bucket Sort	O(n+k)	O(n+k)	O(n^2)	O(n+k)	Yes	Uniform distribution

---

Graph Algorithm Complexities

Algorithm	Time	Space	Notes
BFS / DFS	O(V+E)	O(V)	Adj list; O(V^2) with adj matrix
Topological Sort	O(V+E)	O(V)	DAG only
Dijkstra (binary heap)	O((V+E) log V)	O(V)	Non-negative weights
Dijkstra (Fibonacci heap)	O(E + V log V)	O(V)	Theoretical, rarely used
Bellman-Ford	O(VE)	O(V)	Handles negative weights
Floyd-Warshall	O(V^3)	O(V^2)	All pairs
Kruskal's MST	O(E log E)	O(V)	With Union-Find
Prim's MST	O((V+E) log V)	O(V)	With binary heap
Union-Find (ops)	O(alpha(n)) ~ O(1)	O(n)	Per operation, amortized

---

Space Complexity Rules of Thumb

Structure / Operation	Space
Recursion depth d	O(d) stack frames
DFS on tree	O(h) where h = height (O(log n) balanced, O(n) skewed)
BFS on tree	O(w) where w = max width (up to O(n/2) = O(n))
BFS on graph	O(V) for visited set + queue
Hash map of n items	O(n)
2D DP table n x m	O(nm) -- optimize to O(min(n,m)) with rolling array
Adjacency list	O(V+E)
Adjacency matrix	O(V^2)
Sorting (Timsort)	O(n) auxiliary
Heap	O(n) to store, O(1) auxiliary for operations
Trie of k words, avg len L	O(k * L) worst case

Recursion Stack Depth

• Python default recursion limit: 1000
• Increase with: import sys; sys.setrecursionlimit(10**6)
• Better: convert to iterative with explicit stack for deep recursion

Common Space Optimizations

• DP rolling array: O(nm) -> O(m) when row i depends only on row i-1
• Bit manipulation: Use int as bitset (Python ints are arbitrary precision)
• In-place modification: Mark visited in grid with sentinel value
• Generator/iterator: Process stream without storing all in memory