Quick Reference Card
Time Complexity Limits
| Constraint | Max Complexity | Example Algorithm |
|---|---|---|
| n ≤ 10 | O(n!) | Brute force permutations |
| n ≤ 20 | O(2^n × n) | Bitmask DP |
| n ≤ 100 | O(n³) | Floyd-Warshall |
| n ≤ 500 | O(n³) | Matrix chain DP |
| n ≤ 3,000 | O(n²) | 2D DP, all pairs |
| n ≤ 10⁵ | O(n log n) | Sorting, segment tree |
| n ≤ 10⁶ | O(n) | Linear algorithms |
| n ≤ 10⁸ | O(n) careful | Very simple O(n) |
| n ≤ 10⁹ | O(√n) or O(log n) | Binary search, math |
| n ≤ 10¹⁸ | O(log n) | Binary exponentiation |
Common Constants
STL Complexity Reference
vector
| Operation | Complexity |
|---|---|
push_back | O(1) amortized |
pop_back | O(1) |
Access [i] | O(1) |
insert at position | O(n) |
erase at position | O(n) |
size | O(1) |
set / map
| Operation | Complexity |
|---|---|
insert | O(log n) |
find | O(log n) |
erase | O(log n) |
lower_bound | O(log n) |
begin / rbegin | O(1) |
unordered_set / unordered_map
| Operation | Complexity |
|---|---|
insert | O(1) avg, O(n) worst |
find | O(1) avg, O(n) worst |
erase | O(1) avg |
priority_queue
| Operation | Complexity |
|---|---|
push | O(log n) |
pop | O(log n) |
top | O(1) |
Binary Search Templates
Lower Bound (First ≥ target)
Upper Bound (First > target)
Binary Search on Answer
Graph Templates
DFS
BFS
Dijkstra
Number Theory Formulas
GCD / LCM
Modular Exponentiation
Modular Inverse (p prime)
Combinations (nCr)
Check Prime
Bit Manipulation
String Patterns
String to Int/LL
Int to String
Split by Delimiter
Check Palindrome
Direction Arrays
Common Patterns
Coordinate Compression
Prefix Sum
Two Pointers
Output Formatting
Contest Checklist
Back to Overview
Return to the course curriculum.