How to Read Constraints to Guess the Expected Time Complexity

You can guess the expected time complexity of any coding problem by looking at the input size before you write a single line of code. When the limits on $n$ are clear in the problem statement, the intended algorithm is already decided for you. Stop guessing between brute force and dynamic programming during your placement tests, and use the numbers in the constraints as your primary guide.

The Rule of $n$

Input limits map directly to computational steps. A modern CPU handles roughly $10^8$ operations per second in standard online judges like Codeforces or LeetCode.

When $n$ is up to $20$, your solution can be exponential like $O(2^n)$. An input of $20$ means $2^{20}$ operations, which equals $1,048,576$ steps. That runs in a few milliseconds. If $n$ is $100$, an exponential approach fails instantly because $2^{100}$ exceeds the atoms in the universe.

When $n$ is up to $10^3$, you need $O(n^2)$ or $O(n \log n)$. This limit appears frequently in matrix problems or grid traversals where you compare every pair of elements. An $n$ of $1000$ squared gives $10^6$ operations, which fits safely inside the one-second time limit.

When $n$ is up to $10^5$ or $10^6$, any quadratic solution receives a time limit exceeded error. You must use $O(n \log n)$ or strict $O(n)$ time. Sorting an array of size $10^5$ takes roughly $10^5 \log_2(10^5)$ steps, which is about $1.7 \times 10^6$ operations. That is fast.

When $n$ is up to $10^9$ or larger, linear scan is too slow. You require $O(\log n)$ using binary search, or $O(1)$ using direct mathematical formulas. If the limit is $10^9$, checking every number one by one takes ten seconds. Binary search on $10^9$ takes at most $30$ steps.

Worked Example

Consider a problem titled Two Sum where the input array has length $n$ up to $10^5$ and target values fit in standard integer ranges.

If you use a nested loop to check every pair, your code runs in $O(n^2)$ time. For $10^5$ elements, $n^2$ equals $10^{10}$ operations. The judge will reject it.

The constraint of $10^5$ forces you to choose $O(n)$ or $O(n \log n)$. You store each number in a hash map as you iterate through the array of size $10^5$, checking if target - current_element exists in the map. This single pass takes $O(n)$ time and executes in less than fifty milliseconds.

The Constraint Cheat Sheet

• $n \le 20$: $O(2^n)$ or $O(n!)$ for backtracking and subsets
• $n \le 500$: $O(n^3)$ for dynamic programming on intervals or matrix multiplication
• $n \le 5000$: $O(n^2)$ for nested loops on strings and arrays
• $n \le 10^6$: $O(n \log n)$ or $O(n)$ for sorting, two pointers, and heaps
• $n > 10^8$: $O(\log n)$ or $O(1)$ for binary search and arithmetic formulas

Common Exceptions

Sometimes the constraints lie. A problem might say $n \le 10^5$, but an internal condition states that all array elements are distinct and chosen from a range of $1$ to $10$. That lets you use counting sort or frequency arrays in $O(n)$ time.

Another exception involves bit manipulation or segment trees where a factor of $32$ or $64$ comes from the word size of the machine. An $O(32n)$ solution looks like $O(n)$ in practice. Always check if the operations inside the loop are bitwise shifts or simple additions because bitwise operations run faster than standard division.

Open DSA Tracker and sort your next practice session by constraint size instead of topic name.

Keep going with practice problems and the online compiler.

Further reading: Binary search on Wikipedia.