Reading a problem's constraints
Use n's upper limit to work out which complexity the intended solution must have.
Big idea
A problem's limits — 1 ≤ n ≤ 10^5, n ≤ 20 — are a hint about the intended algorithm. With a budget of roughly 10⁸ simple steps per second, the size of n tells you the slowest complexity that will still pass.
The budget
A judge typically allows 1–2 seconds and does around 10⁸ simple operations per second (C++ a bit more, Python noticeably fewer — budget about 10⁷ for Python). So work out how many steps your idea needs at the largest n, and compare.
The cheat sheet
| Largest n | Fastest growth that fits | Typical techniques |
|---|---|---|
| n ≤ 10 | O(n!) | try every ordering (permutations) |
| n ≤ 20 | O(2ⁿ) or O(2ⁿ × n) | every subset, bitmask DP, backtracking |
| n ≤ 500 | O(n³) | triple loops, interval DP, Floyd-Warshall |
| n ≤ 5,000 | O(n²) | all pairs, 2D DP |
| n ≤ 10⁶ | O(n log n) | sorting, heaps, binary search, divide and conquer |
| n ≤ 10⁸ | O(n) | one pass, two pointers, sliding window, hashing |
| n up to 10¹⁸ | O(log n) or O(1) | binary search on the answer, fast exponentiation, math |
Read it both ways. If n ≤ 10^5, an O(n²) idea (10¹⁰ steps) won't pass — look for O(n log n) or O(n). If n ≤ 15, the problem is inviting you to try all 2¹⁵ = 32,768 subsets.
Watch it
Worked examples
"Given an array of up to 10⁵ integers, count pairs that sum to k." Checking every pair is 5 × 10⁹ — too slow. You need O(n) or O(n log n): a hash map of counts, or sorting plus two pointers.
"Given up to 15 tasks, find the best order." 15! is 1.3 trillion, too slow; but 2¹⁵ × 15 ≈ 500,000 fits — a bitmask DP over subsets of finished tasks.
"Given n up to 10¹⁸, compute something." You can't even loop to n. The answer is a formula, or O(log n) — binary search or repeated squaring.
Other limits to read
- Value ranges. If values are
0 ≤ x ≤ 1000, a counting array of size 1,001 replaces a hash map or a sort. - Two sizes. "A string of length n ≤ 1000 and a word list of m ≤ 1000": n × m = 10⁶ is fine.
- Number of queries. "Up to 10⁵ range-sum queries on an array of 10⁵": recomputing each sum is 10¹⁰. Precompute once — prefix sums, or a Fenwick tree if the array also changes.
- Sum of lengths. "The total length of all strings is at most 10⁶" means you can afford to touch every character a constant number of times.
- Overflow. Values up to 10⁹ and sums of up to 10⁵ of them reach 10¹⁴ — beyond a 32-bit int (about 2.1 × 10⁹). Use 64-bit integers.
In an interview
There's often no written limit. Ask: "How large can the input get?" The answer tells you whether the O(n²) brute force is acceptable or a stepping stone. Then state your final complexity and check it against that size out loud.
Quick check
A problem says n ≤ 2 × 10^5. Which is the slowest complexity that will comfortably pass?
A problem limits n to at most 18. What does that suggest?
You sum up to 10^5 values, each up to 10^9. Will the total fit in a 32-bit signed integer (max ≈ 2.1 × 10^9)?