← all cheatsheets

cheatsheet · before you code

How fast must it be?

Use it when: You've read the constraints (n ≤ …) and want to know which complexity will pass.

  1. n ≤ 10O(n!)permutations, brute-force backtracking
  2. n ≤ 20O(2ⁿ)subsets, bitmask DP
  3. n ≤ 500O(n³)Floyd–Warshall, interval DP
  4. n ≤ 5·10³O(n²)2D DP, all pairs
  5. n ≤ 10⁶O(n log n)sorting, heaps, binary search
  6. n ≤ 10⁸O(n)one pass, two pointers, hashing
  7. n > 10⁸O(log n) / O(1)math, binary search on the answer

How to use it, in three steps

  1. Find the biggest number in the constraints, e.g. 1 ≤ n ≤ 10⁵.
  2. Find its row. 10⁵ sits under 10⁶, so O(n log n) is fine.
  3. Check your idea: O(n²) would be 10¹⁰ steps, about 100 seconds in Java. Too slow. O(n log n) is about 1.7·10⁶ steps. Easy.

These are rules of thumb: Java does roughly 10⁸ simple steps a second, and judges allow about 1–2 seconds. Several inputs (two arrays, a grid) multiply: an m × n grid with both ≤ 10³ is 10⁶ cells.