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 Input | Worst Accepted Algorithm |
|---|---|
| <= 11 | O(N!), O(n^6) |
| <= 18 | O(2^N * N^2) |
| <= 22 | O(2^N * N) |
| <= 100 | O(N^4) |
| <= 400 | O(N^3) |
| <= 2K | O(N^2 * logN) |
| <= 10K | O(N^2) |
| <= 1M | O(N * logN) |
| <= 100M | O(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.