It is very important to understand the complexity of the algorithm that we want to implement and to understand if it would pass on the constraints given in the problem set. This should be done "mentally", without needing to implement and testing empirically.
Here I provide a "guiding table" that estimates the limits for the most usual complexities. It is not possible to be much precise, because of the "scale" factor (ex: higher constant on the algorithm). Also note that the exact time limit for the problem and the exact processor being used might change the values by a certain factor. However, the magnitude of the limits is the same and thus this table can be useful at the beginning of your journey competitive programming. We assume +/- 10^8 instructions per second as a plausible estimate, and we show the maximum size of the problems we could tackle:
| Complexity | Description | Maximum N to pass this time limit | Example Algorithm | |
|---|---|---|---|---|
| 1s | 5s | |||
| O(1) | constant | ∞ (infinity) | ∞ (infinity) | summing two numbers |
| O(log N) | logarithmic | 2^(10^8) | 2^(5x10^8) | binary search |
| O(N) | linear | 10^8 | 5x10^8 | 1 cycle to find the maximum |
| O(N log N) | linearithmic | 4.523.071 | 20.5805.53 | sorting (ex: mergesort, heapsort) |
| O(N^2) | quadratic | 10.000 | 22.360 | 2 cycles (ex: verifying pairs) |
| O(N^3) | cubic | 464 | 793 | 3 cycles (ex: Floyd-Warshall) |
| O(2^N) | exponential | 26 | 28 | exhaustive search (ex: subsets) |
| O(N!) | factorial | 11 | 12 | generating all permutations |
From now on, everytime you solve a problem, try to estimate beforehand how much time your algorithm would take and then verify if your estimate was correct. With more experience, you will notice that you will be able to figure our the desired complexity for the given constraints of the problem.
Pedro Ribeiro - DCC/FCUP | Último update: