Guide to Competitive Programming

By calculating the time complexity of an algorithm, it is possible to check, before implementing the algorithm, that it is efficient enough for solving a problem. The starting point for estimations is the fact that a modern computer can perform some hundreds of millions of simple operations in a second.

For example, assume that the time limit for a problem is one second and the input size is n = 105. If the time complexity is O(n2), the algorithm will perform about (105)2 = 1010 operations. This should take at least some tens of seconds, so the algorithm seems to be too slow for solving the problem. However, if the time complexity is O(n log n), there will be only about 105 log 105 ≈ 1.6·106 operations, and the algorithm will surely fit the time limit.

On the other hand, given the input size, we can try to guess the required time complexity of the algorithm that solves the problem. Table 3.1 contains some useful estimates assuming a time limit of one second.

For example, if the input size is n = 105, it is probably expected that the time complexity of the algorithm is O(n) or O(n log n). This information makes it easier to design the algorithm, because it rules out approaches thatwould yield an algorithm with a worse time complexity.

Still, it is important to remember that a time complexity is only an estimate of efficiency, because it hides the constant factors. For example, an algorithm that runs in O(n) time may perform n/2 or 5n operations, which has an important effect on the actual running time of the algorithm.

Estimating time complexity from input size