Lesson 42.2 · Pattern Recognition Drills
Constraints Tell You the Complexity
About 10⁸ simple operations run in a second. Divide that by n and you know which complexities fit, and therefore which patterns are even possible.
10 min
Think of it like this
A delivery driver with one hour can't visit every house in the city, but can visit every house on one street. The time limit tells you how big a route you're allowed to plan.
1.A quick table
n ≤ 10–12 → O(n!) permutations. n ≤ 20–25 → O(2ⁿ) subsets, bitmask DP. n ≤ 40 → meet in the middle (2^(n/2)). n ≤ 500 → O(n³) (interval DP, Floyd-Warshall). n ≤ 5000 → O(n²) DP. n ≤ 10⁵–10⁶ → O(n log n) or O(n): sorting, heaps, binary search, sliding windows, hashing, linear DP. n ≤ 10⁹ or more → O(log n) or O(√n): binary search on the answer, math.
Values matter too: a sum up to 10⁴ allows a knapsack table; values up to 10⁹ do not. "Return modulo 10⁹ + 7" means the true answer is huge, so it's counting (DP or combinatorics), not enumeration.
Quick check
n ≤ 15 and you must assign every item to a group. Which pattern is likely?
Remember
- ~10⁸ operations per second.
- n decides the complexity class.
- "mod 10⁹ + 7" ⇒ counting.
Common mistakes
- Optimising an O(n²) idea for n = 10⁵ instead of looking for an O(n log n) pattern.