Guide to Competitive Programming

What does it exactly mean that an algorithm works in O( f (n)) time? It means that there are constants c and n0 such that the algorithm performs at most c f (n) operations for all inputs where n ≥ n0. Thus, the O notation gives an upper bound for the running time of the algorithm for sufficiently large inputs.

For example, it is technically correct to say that the time complexity of the following algorithm is O(n2).

for (int i = 1; i <= n; i++) {

}

However, a better bound is O(n), and it would be very misleading to give the bound O(n2), because everybody actually assumes that the O notation is used to give an accurate estimate of the time complexity.

There are also two other common notations. The Ω notation gives a lower bound for the running time of an algorithm. The time complexity of an algorithm isΩ( f (n)), if there are constants c and n0 such that the algorithm performs at least c f (n) operations for all inputs where n ≥ n0.

Finally, the Θ notation gives an exact bound: the time complexity of an algorithm is Θ( f (n)) if it is both O( f (n)) and Ω( f (n)).
For example, since the time complexity of the above algorithm is both O(n) and Ω(n), it is also Θ(n).

We can use the above notations in many situations, not only for referring to time complexities of algorithms. For example, we might say that an array contains O(n) values, or that an algorithm consists of O(log n) rounds.