⚡ Complexity Cheatsheet

Quick Reference

Dùng file này như một “cheat sheet” trong interview prep. In ra hoặc pin lên màn hình. ← Roadmap-FAANG

---

Constraint → Algorithm Map

Input Size $N$	Max Complexity	Algorithms
$N\le 10$	$O(N!)$	Permutations, brute force
$N\le 15$	$O(2^N\cdot N)$	Bitmask DP with transitions
$N\le 20$	$O(2^N)$	Subset enumeration, Bitmask DP
$N\le 100$	$O(N^3)$	Floyd-Warshall, 3D DP
$N\le 400$	$O(N^3)$	Matrix chain multiplication DP
$N\le 1000$	$O(N^2)$	Bubble/Insertion sort, $O(N^2)$ DP
$N\le 10^4$	$O(N^2)$	String matching naive, 2D grid BFS
$N\le 10^5$	$O(N\log N)$	Merge sort, Heap, Segment Tree, Dijkstra
$N\le 10^6$	$O(N)$	Two pointers, Sliding window, Linear sort
$N\le 10^9$	$O(\log N)$	Binary search, Fast exponentiation
$N\le 10^{18}$	$O({\log }^{2}N)$	Binary search on answer + check

---

Data Structure Complexities

Array / Dynamic Array

Operation	Average	Worst
Access	$O(1)$	$O(1)$
Search	$O(N)$	$O(N)$
Insert (end)	$O(1)$ amortized	$O(N)$
Insert (middle)	$O(N)$	$O(N)$
Delete	$O(N)$	$O(N)$

Linked List

Operation	Average	Notes
Access	$O(N)$	No random access
Search	$O(N)$
Insert (head)	$O(1)$
Insert (tail with tail pointer)	$O(1)$
Insert (middle — after finding node)	$O(1)$	Finding is $O(N)$

Hash Table

Operation	Average	Worst (hash collision)
Search	$O(1)$	$O(N)$
Insert	$O(1)$	$O(N)$
Delete	$O(1)$	$O(N)$

Hash Map trong JS/TS

Map<K,V> và Set<T> đều $O(1)$ average. Tránh dùng plain object {} cho numeric keys vì key order behavior khác.

Binary Search Tree (Balanced — AVL/Red-Black)

Operation	Average	Worst
Search	$O(\log N)$	$O(\log N)$
Insert	$O(\log N)$	$O(\log N)$
Delete	$O(\log N)$	$O(\log N)$

Heap (Binary Heap)

Operation	Complexity
Build heap	$O(N)$
Insert	$O(\log N)$
Get min/max	$O(1)$
Extract min/max	$O(\log N)$
Decrease key	$O(\log N)$

Graph

Algorithm	Time	Space	Use Case
BFS	$O(V+E)$	$O(V)$	Shortest path (unweighted)
DFS	$O(V+E)$	$O(V)$	Cycle detection, topo sort
Dijkstra	$O(E\log V)$	$O(V+E)$	Shortest path (non-negative weights)
Bellman-Ford	$O(VE)$	$O(V)$	Shortest path (negative weights)
Floyd-Warshall	$O(V^3)$	$O(V^2)$	All-pairs shortest path
Prim’s MST	$O(E\log V)$	$O(V+E)$	Minimum spanning tree
Kruskal’s MST	$O(E\log E)$	$O(V+E)$	Minimum spanning tree

Sorting

Algorithm	Best	Average	Worst	Space	Stable?
Merge Sort	$O(N\log N)$	$O(N\log N)$	$O(N\log N)$	$O(N)$	✅
Quick Sort	$O(N\log N)$	$O(N\log N)$	$O(N^2)$	$O(\log N)$	❌
Heap Sort	$O(N\log N)$	$O(N\log N)$	$O(N\log N)$	$O(1)$	❌
Tim Sort (JS default)	$O(N)$	$O(N\log N)$	$O(N\log N)$	$O(N)$	✅
Counting Sort	$O(N+K)$	$O(N+K)$	$O(N+K)$	$O(K)$	✅
Radix Sort	$O(NK)$	$O(NK)$	$O(NK)$	$O(N+K)$	✅

---

Recursion & DP Space Complexity

Type	Space
Recursion depth	$O(\text{depth})$ — thường là $O(N)$ hoặc $O(\log N)$
Memoization (top-down DP)	$O(\text{states})$ + $O(\text{depth})$ call stack
Tabulation (bottom-up DP)	$O(\text{states})$ — no call stack overhead
Space-optimized DP (1D rolling)	$O(\text{single row/col})$

---

String Algorithms

Algorithm	Time	Use Case
Naive pattern match	$O(NM)$	Simple, small inputs
KMP	$O(N+M)$	Pattern matching
Rabin-Karp (Rolling Hash)	$O(N+M)$ avg	Multiple pattern search
Z-algorithm	$O(N+M)$	Pattern matching
Trie insert/search	$O(L)$	Prefix search, $L$ = word length
Suffix Array	$O(N\log N)$ build	Advanced string problems

---

Master Theorem (Divide & Conquer)

Với recurrence: $T(N)=aT(N/b)+O(N^d)$

Condition	Result
$d>{\log }_{b}a$	$T(N)=O(N^d)$
$d={\log }_{b}a$	$T(N)=O(N^d\log N)$
$d<{\log }_{b}a$	$T(N)=O(N^{{\log }_{b}a})$

Common examples:

• Merge Sort: $T(N)=2T(N/2)+O(N)$ → $d=1,{\log }_{b}a=1$ → $O(N\log N)$
• Binary Search: $T(N)=T(N/2)+O(1)$ → $O(\log N)$

---

← Roadmap-FAANG | 01-Complexity-and-Array →