Constraints and Time Complexity

Solving problems using problem constraints as a guide.

I want to share a strategy for matching input size with suitable time complexity. Often, we learn about time complexity without understanding which one is appropriate for different input sizes.

Here’s a quick guide to help you choose the right time complexity for your problem:

Size of InputWorst Accepted Algorithm
<= 11O(N!), O(n^6)
<= 18O(2^N * N^2)
<= 22O(2^N * N)
<= 100O(N^4)
<= 400O(N^3)
<= 2KO(N^2 * logN)
<= 10KO(N^2)
<= 1MO(N * logN)
<= 100MO(N), O(logN)

Reference: Hackerearth

For example, if you see constraints like N>10^4, aim for at least O(N * logN) or better. If N<1000, a nested loop is likely okay.

For binary search, check out this resource.

This table is especially useful in timed assessments where problem tags may not be available.