Complexity Cheatsheet

What fits in one second

Assume roughly $10^8$ simple operations per second (more for tight loops, fewer with heavy constants).

Complexity	Feasible $n$
$O(1)$, $O(\log n)$	any
$O(\sqrt{n})$	$10^{16}$
$O(n)$	$10^8$
$O(n\log n)$	$10^6$–$10^7$
$O(n\sqrt{n})$	$10^5$
$O(n{\log }^{2}n)$	$10^6$
$O(n^2)$	$5000$
$O(n^2\log n)$	$2000$
$O(n^3)$	$400$
$O(n^4)$	$100$
$O(2^n)$	$25$
$O(2^{n}n)$	$22$
$O(2^n{n}^2)$	$18$
$O(3^n)$	$16$
$O(n!)$	$11$
$O(n^n)$	$8$

Read the constraint, pick the row, and that is your target complexity.

Memory

Type	Elements in 256 MB
bool / char	$2.6\cdot 10^8$
short	$1.3\cdot 10^8$
int / float	$6.7\cdot 10^7$
long long / double	$3.3\cdot 10^7$
bitset bits	$2.1\cdot 10^9$
pair<int,int>	$3.3\cdot 10^7$

Rules of thumb: a long long table of $5000\times 5000$ is 200 MB (too big); as int it is 100 MB (borderline); rolled to two rows it is 40 KB.

vector has ~24 bytes of overhead each, so vector<vector<int>> with $10^6$ rows costs 24 MB before any data.

Data structure operations

Structure	Build	Query	Update	Space
Prefix sum	$O(n)$	$O(1)$	✘	$O(n)$
Sparse table	$O(n\log n)$	$O(1)$	✘	$O(n\log n)$
Fenwick tree	$O(n)$	$O(\log n)$	$O(\log n)$	$O(n)$
Segment tree	$O(n)$	$O(\log n)$	$O(\log n)$	$O(n)$
Lazy segtree	$O(n)$	$O(\log n)$	$O(\log n)$ range	$O(n)$
Sqrt decomposition	$O(n)$	$O(\sqrt{n})$	$O(1)$–$O(\sqrt{n})$	$O(n)$
DSU	$O(n)$	$O(\alpha )$	$O(\alpha )$	$O(n)$
Heap	$O(n)$	$O(1)$ top	$O(\log n)$	$O(n)$
`set`/`map`	—	$O(\log n)$	$O(\log n)$	$O(n)$
unordered_map	—	$O(1)$ avg	$O(1)$ avg	$O(n)$
Trie	$O(\sum |w|)$	$O(|w|)$	$O(|w|)$	$O(\sigma \sum |w|)$
Persistent segtree	$O(n\log n)$	$O(\log n)$	$O(\log n)$ new nodes	$O(n\log n)$
HLD + segtree	$O(n)$	$O({\log }^{2}n)$	$O({\log }^{2}n)$	$O(n)$

Sorting and searching

Algorithm	Time	Space	Stable
std::sort (introsort)	$O(n\log n)$	$O(\log n)$	✘
stable_sort	$O(n\log n)$	$O(n)$	✔
nth_element	$O(n)$ expected	$O(1)$	✘
partial_sort (top $k$)	$O(n\log k)$	$O(1)$	✘
Counting sort	$O(n+k)$	$O(k)$	✔
Radix sort	$O(n\cdot w/b)$	$O(n+2^b)$	✔
Binary search	$O(\log n)$	$O(1)$	—

Graph algorithms

See Graph Complexity Cheatsheet for the full table.

Algorithm	Time
DFS / BFS	$O(V+E)$
Dijkstra	$O(E\log V)$
Bellman-Ford	$O(VE)$
Floyd-Warshall	$O(V^3)$
Kruskal	$O(E\log E)$
SCC	$O(V+E)$
Dinic	$O(V^{2}E)$, $O(E\sqrt{V})$ unit
Hungarian	$O(V^3)$

Useful magnitudes

Quantity	Value
INT_MAX	$2.1\cdot 10^9$
LLONG_MAX	$9.2\cdot 10^{18}$
__int128 max	$1.7\cdot 10^{38}$
double exact integers	up to $2^{53}\approx 9\cdot 10^{15}$
$2^{10}$, $2^{20}$, $2^{30}$	$10^3$, $10^6$, $10^9$
${\log }_2(10^6)$, ${\log }_2(10^9)$, ${\log }_2(10^{18})$	20, 30, 60
$\pi (10^6)$ (primes below)	78 498
Max divisors below $10^{18}$	103 680
$20!$	$2.4\cdot 10^{18}$ (fits); $21!$ overflows
$\left(\genfrac{}{}{0ex}{}{60}{30}\right)$	$1.2\cdot 10^{17}$
$\alpha (n)$ (inverse Ackermann)	$<5$ for any real $n$

Amortized vs worst case

Structure	Note
vector::push_back	$O(1)$ amortized, $O(n)$ worst
DSU	$O(\alpha )$ amortized
Splay / link-cut tree	$O(\log n)$ amortized, $O(n)$ single op
Monotonic stack	$O(n)$ total, not per operation
Segment tree beats	$O({\log }^{2}n)$ amortized
Hash table	$O(1)$ expected, $O(n)$ worst

Amortized bounds are fine for total-time limits; they matter only in real-time or interactive settings.

See also: Complexity Theory · Problem Pattern Recognition · Graph Cheatsheet