Chapter 138
HomeThe constraints tell you the algorithm. Before writing code, check N and estimate acceptable complexity. ~10⁸ operations per second in C++, ~5×10⁷ in Rust.
N ≤ 10: O(N!) — permutations, brute force N ≤ 20: O(2ᴺ) — subset enumeration, bitmask DP N ≤ 100: O(N³) — Floyd-Warshall, matrix multiplication N ≤ 1000: O(N²) — nested loops, basic DP N ≤ 10⁵: O(N log N) — sorting, segment tree, Dijkstra N ≤ 10⁶: O(N) — linear scan, prefix sums, BFS/DFS N ≤ 10⁷: O(N log N) borderline — careful with constants N ≤ 10⁸: O(N) — fast I/O required N ≥ 10⁹: O(log N) or O(1) — binary search, math formula