# Reading Constraints to Pick an Approach — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/p-constraints

> Estimate feasible complexity from input limits and time limits.

## 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.

```text
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).

**Quiz:** A problem has n ≤ 200,000 and a one-second limit. Which complexity is most likely expected?

- [ ] O(n³)
- [x] O(n log n)
- [ ] O(2ⁿ)
- [ ] O(n!)

*Answer:* O(n log n). With n around 2 × 10⁵, O(n²) is about 4 × 10¹⁰ operations, too many; O(n log n) fits easily.