Reading Constraints to Pick an Approach

Let the limits guide you

Competitive programming and interview problems give constraints such as n ≤ 10⁵ and a time limit of one or two seconds. A rough rule of thumb is that a typical machine performs on the order of 10⁸ simple operations per second in a compiled language (fewer in Python, often by a factor of 10 to 50). Working backwards: n ≤ 10 or 11 allows O(n!) permutations; n ≤ 20 allows O(2ⁿ) subsets or bitmasks; n ≤ 500 allows O(n³); n ≤ 5,000 allows O(n²); n ≤ 10⁵ to 10⁶ needs O(n log n) or O(n); n ≤ 10⁸ or more needs O(n) with small constants, O(log n) or O(1) maths. These are guidelines, not laws: constant factors, memory access patterns and language matter. The same reasoning helps in real systems: if a nightly job must process 50 million rows in an hour, you know immediately that an O(n²) step is impossible and an O(n log n) step is comfortable.

Constraint-to-complexity guide

Approximate limits for about one second in a fast language.

max n          feasible complexity     typical techniques
-------------  ----------------------  -----------------------------------------
<= 10-11       O(n!)                   permutations, brute force
<= 20-25       O(2^n), O(2^n * n)      subsets, bitmask DP, backtracking
<= 500         O(n^3)                  Floyd-Warshall, interval DP
<= 5,000       O(n^2)                  pairwise DP, simple nested loops
<= 10^5-10^6   O(n log n), O(n)        sorting, heaps, binary search, two pointers
<= 10^8+       O(n) small constant,    prefix sums, maths formulas, streaming
               O(log n), O(1)

Python: divide these budgets by roughly 10-50 for pure-Python loops

Packing for a trip

The constraints are the size of your suitcase. Knowing it in advance tells you whether to bring the full wardrobe (brute force) or only the essentials (an efficient algorithm).

त्वरित जाँच: A problem has n ≤ 200,000 and a one-second limit. Which complexity is most likely expected?

• O(n³)
• O(n log n)
• O(2ⁿ)
• O(n!)