Complexity Cheatsheet

Quick reference for time and space complexities of every structure and algorithm in this guidebook, plus the maximum- $n$ table you scan to reject impossible approaches.

Quick Revisit
Scan the Maximum N table first to reject infeasible approaches given the problem's constraints.
All entries are baseline complexities. Constants and time limits matter — see the constant-factor notes after the table.
This file is a pure reference. For decision-making about which approach to pick, see Chapter 10 (Patterns) and the DS Selection Guide.

CF Rating Range: 1100 -- 2100

Big-O Quick Reference
Data Structure Complexities
Algorithm Complexities
DP Complexities
Maximum N Guidelines
What the Code Won't Teach You
Self-Test
See Also

Big-O Quick Reference

How large can $n$ be for each complexity class within a ~1--2 second time limit (assuming $\sim 10^{8}$ simple operations per second)?

Caveat. Numbers below assume tight inner loops over basic types. The same $O (n \log n)$ bound at $n = 5 \times 10^{6}$ is comfortable for a plain sort but tight for a segment tree carrying 64-byte structs. When in doubt, multiply out the operation count and sanity-check the per-operation cost.

+------------------+------------------+-------------------------------------------+
| Complexity       | Max n (~1-2 sec) | Typical use case                          |
+------------------+------------------+-------------------------------------------+
| O(1)             | any              | Hash lookup, math formula                 |
| O(log n)         | any              | Binary search, balanced BST query         |
| O(sqrt(n))       | ~10^14           | Square-root decomposition, prime check    |
| O(n)             | ~10^8            | Linear scan, prefix sums, counting sort   |
| O(n log n)       | ~5 * 10^6        | Sorting, segment tree build, merge sort   |
| O(n sqrt(n))     | ~5 * 10^5        | Mo's algorithm, sqrt decomposition        |
| O(n^2)           | ~10^4            | Brute-force pairs, 2D DP                  |
| O(n^2 log n)     | ~5 * 10^3        | Convex hull trick with sorting            |
| O(n^3)           | ~500             | Floyd-Warshall, matrix mult, 3D DP       |
| O(n^4)           | ~100             | 4-nested loops, interval DP variants      |
| O(2^n)           | ~25              | Subset enumeration                        |
| O(2^n * n)       | ~20-23           | Bitmask DP, TSP                           |
| O(n!)            | ~10-11           | Permutation brute force                   |
| O(n^n)           | ~8               | Brute force with repetition               |
+------------------+------------------+-------------------------------------------+

Data Structure Complexities

All complexities are worst-case unless marked (amortized) or (average).

Sequential Containers

+----------------+-----------+-----------+----------+----------+----------+--------+
| Structure      | Access    | Search    | Insert   | Delete   | PushBack | Space  |
+----------------+-----------+-----------+----------+----------+----------+--------+
| vector         | O(1)      | O(n)      | O(n)     | O(n)     | O(1)*    | O(n)   |
| deque          | O(1)      | O(n)      | O(n)     | O(n)     | O(1)*    | O(n)   |
| list           | O(n)      | O(n)      | O(1)     | O(1)     | O(1)     | O(n)   |
+----------------+-----------+-----------+----------+----------+----------+--------+
  * = amortized

Associative / Hash Containers

+--------------------+------------+------------+------------+------------+---------+
| Structure          | Search     | Insert     | Delete     | Iterate    | Space   |
+--------------------+------------+------------+------------+------------+---------+
| set / multiset     | O(log n)   | O(log n)   | O(log n)   | O(n)       | O(n)    |
| map                | O(log n)   | O(log n)   | O(log n)   | O(n)       | O(n)    |
| unordered_map      | O(1) avg   | O(1) avg   | O(1) avg   | O(n)       | O(n)    |
|   (worst case)     | O(n)       | O(n)       | O(n)       |            |         |
+--------------------+------------+------------+------------+------------+---------+

Contest note: unordered_map can be hacked to $O (n)$ per operation on Codeforces with adversarial input. Use a custom hash or fall back to map in interactive/hack-prone rounds.

Heaps & Priority Queues

+-------------------+----------+----------+----------+----------+---------+
| Structure         | FindMin  | Insert   | Extract  | Decrease | Space   |
+-------------------+----------+----------+----------+----------+---------+
| priority_queue    | O(1)     | O(log n) | O(log n) | --       | O(n)    |
|   (binary heap)   |          |          |          |          |         |
+-------------------+----------+----------+----------+----------+---------+

priority_queue does not support decrease-key natively. For Dijkstra, either use lazy deletion or set<pair<int,int>>.

Disjoint Set Union (DSU)

+-------------------+-------------+-------------+---------+
| Operation         | Time        | With path   | Space   |
|                   | (rank only) | + rank      |         |
+-------------------+-------------+-------------+---------+
| Find              | O(log n)    | O(alpha(n)) | O(n)    |
| Union             | O(log n)    | O(alpha(n)) | O(n)    |
+-------------------+-------------+-------------+---------+

$α (n)$ is the inverse Ackermann function -- effectively $O (1)$ for all practical $n$ .

Range Query Structures

+-------------------+-----------+-----------+-----------+---------+
| Structure         | Build     | Query     | Update    | Space   |
+-------------------+-----------+-----------+-----------+---------+
| Prefix sums       | O(n)      | O(1)      | O(n)      | O(n)    |
| BIT (Fenwick)     | O(n)      | O(log n)  | O(log n)  | O(n)    |
| Segment tree      | O(n)      | O(log n)  | O(log n)  | O(4n)   |
|   + lazy prop     | O(n)      | O(log n)  | O(log n)  | O(4n)   |
| Sparse table      | O(n lg n) | O(1)      | --        | O(n lg n)|
+-------------------+-----------+-----------+-----------+---------+

Sparse table is immutable -- use it only when the array never changes (static RMQ).

String Structures

+-------------------+-----------+------------+-----------+---------+
| Structure         | Build     | Search     | Insert    | Space   |
+-------------------+-----------+------------+-----------+---------+
| Trie              | --        | O(|s|)     | O(|s|)    | O(A*N)  |
+-------------------+-----------+------------+-----------+---------+

$A$ = alphabet size, $N$ = total characters inserted. In practice memory is the bottleneck; a trie on lowercase English has $A = 26$ .

Balanced BST / Treap

+-------------------+-----------+-----------+-----------+-----------+---------+
| Structure         | Search    | Insert    | Delete    | Split/    | Space   |
|                   |           |           |           | Merge     |         |
+-------------------+-----------+-----------+-----------+-----------+---------+
| Treap             | O(log n)  | O(log n)  | O(log n)  | O(log n)  | O(n)   |
|   (expected)      |           |           |           |           |         |
+-------------------+-----------+-----------+-----------+-----------+---------+

Treap complexities are expected (randomized). Split and merge make it ideal for implicit key problems (rope, range reverse).

Algorithm Complexities

Sorting

+-------------------+--------------+--------------+-----------+---------+
| Algorithm         | Best         | Average      | Worst     | Space   |
+-------------------+--------------+--------------+-----------+---------+
| std::sort         | O(n log n)   | O(n log n)   | O(n lg n) | O(lg n) |
| stable_sort       | O(n log n)   | O(n log n)   | O(n lg n) | O(n)    |
| Counting sort     | O(n + k)     | O(n + k)     | O(n + k)  | O(k)    |
| Radix sort        | O(d(n + k))  | O(d(n + k))  | O(d(n+k)) | O(n+k)  |
+-------------------+--------------+--------------+-----------+---------+

$k$ = range of values, $d$ = number of digits. std::sort uses introsort (quicksort + heapsort fallback), so worst case is $O (n \log n)$ , not $O (n^{2})$ .

Searching

+-------------------+------------+---------+
| Algorithm         | Time       | Space   |
+-------------------+------------+---------+
| Linear search     | O(n)       | O(1)    |
| Binary search     | O(log n)   | O(1)    |
| Ternary search    | O(log n)   | O(1)    |
+-------------------+------------+---------+

Graph -- Traversal

+-------------------+------------+---------+---------------------------+
| Algorithm         | Time       | Space   | Notes                     |
+-------------------+------------+---------+---------------------------+
| BFS               | O(V + E)   | O(V)    | Unweighted shortest path  |
| DFS               | O(V + E)   | O(V)    | Cycle detect, topo sort   |
| Topological sort  | O(V + E)   | O(V)    | DAG only (Kahn's / DFS)   |
+-------------------+------------+---------+---------------------------+

Graph -- Shortest Path

+-------------------+------------------+---------+------------------------------+
| Algorithm         | Time             | Space   | When to use                  |
+-------------------+------------------+---------+------------------------------+
| BFS (0-1)         | O(V + E)         | O(V)    | Edge weights 0 or 1 only     |
| Dijkstra (heap)   | O((V+E) log V)   | O(V)    | Non-negative weights         |
| Dijkstra (set)    | O((V+E) log V)   | O(V)    | Same, with decrease-key      |
| Bellman-Ford      | O(V * E)         | O(V)    | Negative weights, neg cycle  |
| SPFA              | O(V * E)         | O(V)    | Bellman-Ford + queue (avg    |
|                   |                  |         | faster, same worst case)     |
| Floyd-Warshall    | O(V^3)           | O(V^2)  | All-pairs, V <= 500         |
+-------------------+------------------+---------+------------------------------+

Contest note: SPFA has the same $O (V E)$ worst case as Bellman-Ford. Problem setters on Codeforces frequently add anti-SPFA tests. Prefer Dijkstra when weights are non-negative.

Graph -- MST

+-------------------+-----------------+---------+------------------------------+
| Algorithm         | Time            | Space   | Notes                        |
+-------------------+-----------------+---------+------------------------------+
| Kruskal + DSU     | O(E log E)      | O(V)    | Sort edges, union-find       |
| Prim (heap)       | O((V+E) log V)  | O(V)    | Better for dense graphs      |
+-------------------+-----------------+---------+------------------------------+

String Algorithms

+-------------------+-----------------+---------+------------------------------+
| Algorithm         | Time            | Space   | What it computes             |
+-------------------+-----------------+---------+------------------------------+
| KMP               | O(n + m)        | O(m)    | Pattern matching, fail func  |
| Z-function        | O(n)            | O(n)    | Z-array (longest prefix =    |
|                   |                 |         | substring starting at i)     |
| Rabin-Karp        | O(n + m) avg    | O(1)    | Hashing-based matching       |
| Manacher          | O(n)            | O(n)    | All palindromic substrings   |
| Suffix array      | O(n log n)      | O(n)    | Sorted suffixes              |
|   + LCP           | O(n)            | O(n)    | Longest common prefix array  |
| Aho-Corasick      | O(sum + n + m)  | O(sum*A)| Multi-pattern matching       |
+-------------------+-----------------+---------+------------------------------+

$n$ = text length, $m$ = pattern length, $s u m$ = total pattern length, $A$ = alphabet size.

Number Theory

+--------------------+-----------------+---------+
| Algorithm          | Time            | Space   |
+--------------------+-----------------+---------+
| GCD (Euclidean)    | O(log(min(a,b)))| O(1)    |
| Sieve of Erat.     | O(n log log n)  | O(n)    |
| Fast exponentiation| O(log p)        | O(1)    |
| Modular inverse    | O(log m)        | O(1)    |
| Euler's totient    | O(sqrt(n))      | O(1)    |
| Factorization      | O(sqrt(n))      | O(1)    |
+--------------------+-----------------+---------+

DP Complexities

Common DP patterns with their typical time and space.

+---------------------------+-----------------+-----------+-----------------------+
| DP Variant                | Time            | Space     | Notes                 |
+---------------------------+-----------------+-----------+-----------------------+
| 1D (LIS, coin change)    | O(n^2) or       | O(n)      | O(n log n) LIS with   |
|                           | O(n * W)        |           | patience sorting      |
| Knapsack (0/1)            | O(n * W)        | O(W)      | 1D array trick        |
| Knapsack (unbounded)      | O(n * W)        | O(W)      | Inner loop forward    |
| LCS                       | O(n * m)        | O(min(n,m))| Two strings          |
| Edit distance             | O(n * m)        | O(min(n,m))| Levenshtein          |
| Digit DP                  | O(d * s * t)    | O(d * s)  | d=digits, s=states,   |
|                           |                 |           | t=transitions (0-9)   |
| Bitmask DP                | O(2^n * n)      | O(2^n)    | n <= 20-23            |
| Tree DP                   | O(n)            | O(n)      | One DFS pass          |
| Interval DP               | O(n^3)          | O(n^2)    | Matrix chain style    |
| SOS DP (sum over subsets) | O(2^n * n)      | O(2^n)    | Subset sum queries    |
| Convex hull trick         | O(n log n)      | O(n)      | Optimizes linear DP   |
| Divide & conquer DP       | O(n * m * lg n) | O(n * m)  | Monotone MINIMA       |
| Knuth's optimization      | O(n^2)          | O(n^2)    | Interval DP speedup   |
| Profile DP (broken)       | O(n * m * 2^m)  | O(2^m)    | Grid tiling problems  |
+---------------------------+-----------------+-----------+-----------------------+

Space optimization: Most 2D DP tables where dp[i] depends only on dp[i-1] can be compressed to two rows or a single row. Always check before allocating $O (n \times m)$ .

Maximum N Guidelines

Use this table to instantly estimate feasibility when you read a problem's constraints.

By constraint size

+---------------+--------------------+------------------------------------------+
| n <=          | Affordable         | Example approaches                       |
+---------------+--------------------+------------------------------------------+
| 10            | O(n!) / O(2^n * n) | Brute force all permutations             |
| 15            | O(2^n * n^2)       | Bitmask DP with transitions              |
| 20            | O(2^n * n)         | Bitmask DP (e.g., TSP)                   |
| 23-24         | O(2^n)             | Meet in the middle                       |
| 100           | O(n^3)             | Floyd-Warshall, interval DP              |
| 400-500       | O(n^3)             | Floyd-Warshall (tight), 3D DP            |
| 1000          | O(n^2 log n)       | Sorting + brute-force inner loop         |
| 5000          | O(n^2)             | Pairwise DP, brute-force pairs           |
| 100000        | O(n log n)         | Sorting, segment tree, BIT               |
| 500000        | O(n log n)         | Merge sort, balanced BST operations      |
| 1000000       | O(n)               | Linear scan, two pointers, hashing       |
| 10000000      | O(n)               | Sieve, linear DP (watch constant)        |
| 10^9 or more  | O(log n) / O(1)    | Binary search, math, matrix exponent.    |
+---------------+--------------------+------------------------------------------+

By time limit

+----------------+--------------------------------------------------+
| Time limit     | Rough operation budget                            |
+----------------+--------------------------------------------------+
| 1 second       | ~10^8 simple ops (int add, compare, array access) |
| 2 seconds      | ~2 * 10^8 simple ops                              |
| 3 seconds      | ~3 * 10^8 simple ops                              |
| 4-5 seconds    | ~4-5 * 10^8 (rare on CF, common on ICPC judges)   |
+----------------+--------------------------------------------------+

Constant factor rules of thumb:

Division, modulo: ~2-4x slower than addition.
map / set operations: ~5-10x slower than array access (cache misses + tree overhead).
unordered_map: ~3-5x slower than array access.
Recursive calls: ~2-3x slower than iterative equivalent (function call overhead + stack).
__int128 / big integer: ~4-10x slower than long long.

What the Code Won't Teach You

Insights drawn from reflection notes

$10^{8}$ is a rough guideline, not a hard limit. Actual throughput depends on cache efficiency, operation type, and constant factors. A "tight" $O (n \log n)$ with a bad constant can TLE. A "loose" $O (n \sqrt{n})$ with cache-friendly access can pass. When your operation count is within 5-10x of the limit, worry about constants.

The $n$ in the complexity must match the problem's $n$ . For a graph with $n$ nodes and $m$ edges, " $O (n \log n)$ " might actually be $O ((n + m) \log n)$ . If $m = O (n^{2})$ (dense), this is $O (n^{2} \log n)$ . Always use the right variable.

Constant factors you should estimate:

BIT update/query: ~5-10 simple ops per level
Segment tree: ~20-30 ops per level
Hash map query: ~50-100 ops (cache misses)
std::map lookup: ~30-50 ops (tree pointer chasing)

  THE COMPLEXITY ESTIMATION PIPELINE:

  Read constraints
       │
       ▼
  ┌─────────────────────────────────┐
  │  n <= X  ->  Target complexity?   │
  │  (use the cheat sheet above)    │
  └───────────────┬─────────────────┘
                  │
                  ▼
  ┌─────────────────────────────────┐
  │  Operation count = n x f(n)     │
  │  Does it fit in ~10⁸?           │
  ├──────────┬──────────────────────┤
  │ YES      │ BORDERLINE (10⁷-10⁸)│
  │ proceed  │ check constant factor│
  │          │ cache-friendly?      │
  │          │ heavy inner work?    │
  └──────────┴──────────────────────┘
                  │
                  ▼
  ┌─────────────────────────────────┐
  │  Edge case: does algorithm      │
  │  degrade on worst-case input?   │
  │  (e.g., quicksort on sorted)    │
  └─────────────────────────────────┘

Mental Traps

Integrated from reflection notes

Trap: "My solution is O(n log n), so it will pass."

Only if $n$ is appropriate. $n = 10^{7}$ with $O (n \log n)$ is $\sim 2 \times 10^{8}$ -- marginal. $n = 2 \times 10^{5}$ with $O (n \log n)$ is $\sim 3.4 \times 10^{6}$ -- trivially fine. Always multiply out.

Trap: "O(n²) always means TLE."

$O (n^{2})$ with $n = 3000$ is $9 \times 10^{6}$ -- perfectly fine. With $n = 3 \times 10^{5}$ , it's impossible. The "O(n²) = bad" heuristic only applies to large $n$ .

Trap: "I computed the complexity wrong and don't know it."

Common mistakes: assuming two nested loops are $O (n^{2})$ when the total work is amortized $O (n)$ (monotonic stack), or forgetting that sort inside a loop makes it $O (n^{2} \log n)$ not $O (n^{2})$ .

Trap: "Asymptotic analysis applies to small n."

For $n \leq 100$ , any $O (n^{3})$ solution is trivially fast. Don't optimize what doesn't need it -- complexity analysis matters most when $n$ is near the border.

Trap: "Log factors are free."

You see $n \leq 10^{6}$ and implement $O (n \log^{2} n)$ with a seg tree + binary search. TLE. The double-log killed you: $10^{6} \cdot 20^{2} = 4 \times 10^{8}$ , past the comfort zone. The intended solution was $O (n \log n)$ with a simpler approach. Always check if your log factors fit within $10^{8}$ operations -- an "innocent" extra log can turn AC into TLE at the border of $n$ .

  LOG VALUES TO MEMORIZE:

  ┌────────────┬───────────┐
  │     n      │  log₂(n)  │
  ├────────────┼───────────┤
  │   10³      │    10     │
  │   10⁵      │    17     │
  │   10⁶      │    20     │
  │   10⁹      │    30     │
  │   10¹⁸     │    60     │
  └────────────┴───────────┘

  Quick mental math:
  n=2x10⁵, O(n log²n) = 2x10⁵ x 17² ~= 5.8x10⁷  OK
  n=10⁶,   O(n√n)     = 10⁶ x 10³   = 10⁹       X TLE
  n=5000,  O(n²)       = 2.5x10⁷                  OK

Self-Test

Drawn from reflection notes

[ ] Mental math: For $n = 2 \times 10^{5}$ and TL = 2 seconds, approximately how many $O (n \log^{2} n)$ operations can you afford? Is it within budget?
[ ] Identify the complexity of a monotonic stack: one loop pushes/pops from a stack. Why is it $O (n)$ amortized despite the inner while loop?
[ ] Name three constant-factor situations where actual runtime differs significantly from asymptotic analysis (e.g., cache misses, function call overhead, dynamic allocation).
[ ] Multi-test trap: $t \leq 10^{4}$ test cases, each $n \leq 10^{3}$ . Is $O (n^{2})$ per test case viable? Compute the total and decide.
[ ] Without looking: what is the maximum $n$ for $O (n \sqrt{n})$ to fit in 2 seconds? For $O (2^{n} \cdot n)$ ?

Complexity Cheatsheet ​

Contents ​

Big-O Quick Reference ​

Data Structure Complexities ​

Sequential Containers ​

Associative / Hash Containers ​

Heaps & Priority Queues ​

Disjoint Set Union (DSU) ​

Range Query Structures ​

String Structures ​

Balanced BST / Treap ​

Algorithm Complexities ​

Sorting ​

Searching ​

Graph -- Traversal ​

Graph -- Shortest Path ​

Graph -- MST ​

String Algorithms ​

Number Theory ​

DP Complexities ​

Maximum N Guidelines ​

By constraint size ​

By time limit ​

What the Code Won't Teach You ​

Mental Traps ​

Self-Test ​

See Also ​