Competitive Programming and Time complexity

‘Competitive programming’ is nowadays popular among many coding enthusiasts over the world (including me). It is the skill of designing and implementing efficient algorithms (through code) to solve certain problems. Generally, any problem in competitive programming consists of the following parts:

• The problem statement
• The values to be input and output, and the format in which they will be input/output
• Constraints on the input size (which will help in designing the algorithm, as we will see later)
• Maximum allowable running time and memory space to be used
• Some sample inputs and outputs, which will give a better idea of the problem

To design the algorithm, good logical reasoning skills are required. Implementation, on the other hand, requires knowing and understanding a programming language. Currently the most popular languages for competitive programming are C++, Java and Python. While C++ continues to be the most popular, I use Java, as I have been introduced to it at a young age, and so I am strong in all the language fundamentals. This is important – before choosing a language, you must make sure you can write code efficiently in it.

One important aspect of algorithms is their time complexity, which I will discuss in the following section.

Time complexity

Before I begin, it is expected that you have basic knowledge of Java or any other similar programming language.

Time complexity is a measure of how fast the running time of an algorithm increases with increase in the input size. It is represented by the big-O notation, that is, O(…) where the brackets are filled by some function of the input parameter(s).

Consider the following loop: (assume n is the input)

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

            System.out.println(i);

The number of times the loop executes varies linearly with n, so its time complexity is O(n).

If instead we use two nested loops:

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

            for(int j = 1; j <= n; j++)

                   System.out.println(i);

Then the time complexity will be O(n²) because now the print statement executes n² times.

In general if there are k nested loops of this kind, the time complexity is O(n^k).

It is important to note, however, that time complexity does not give the exact running time of an algorithm – it only gives the order of magnitude. So the following loops all have a time complexity of O(n) each:

for(int i = 1; i <= 5 * n; i++)

            System.out.println(i);

for(int i = 1; i <= n/3; i++)

            System.out.println(i);

for(int i = 1; i <= (20 * n + 4); i++)

            System.out.println(i);

Sometimes the time complexity may depend on more than one input. For example, the time complexity of the following code is O(mn):

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

            for(int j = 1; j <= m; j++)

                  System.out.println(i);

Also, if an algorithm has multiple steps, the overall time complexity is that of the slowest step. For example, if step 1 is O(n), step 2 is O(n²) and step 3 is O(n), then the overall time complexity is O(n²).

The following is a list of complexity classes, from best to the worst:

Complexity	Remarks
O(1)	Constant time algorithm, uses a direct formula (no loops)
O(log n)	Logarithmic, often halves the size of the input at each iteration until it reaches 1 (so number of iterations is about log2n)
O(√n)	Usually a single loop from 1 to √n
O(n)	Usually a single loop from 1 to n
O(n log n)	Time complexity of efficient sorting algorithms (n = number of elements)
O(n2)	Usually two nested loops
O(n3)	Usually three nested loops
O(2n)	Often iterates through all subsets of the input elements (which are n in number)
O(n!)	Often iterates through all permutations of the input elements (which are n in number)

Estimating Efficiency of Algorithms:

In any problem in competitive programming, you are given the time limit for running of the program (usually 1 second) and the constraints on the input data. Also, it is important to know that computers can perform about 10⁷ to 10⁸ individual operations per second. Based on this, some estimates on the time complexity of your algorithm can be made, based on the constraints on the input:

Constraint	Required Time Complexity
n <= 10	O(n!)
n <= 20	O(2n)
n <= 500	O(n3)
n <= 5000	O(n2)
n <= 106	O(n) or O(n log n)
n can be > 106	O(1) or O(log n) (and in some cases O(√n))

However, one important limitation of time complexity is that it hides the constant factors (recall that the time complexity is O(n) whether the loop executes n or 10n or 20n times). These constant factors, though usually small, may have a significant effect on the actual running time of the algorithm.

In this post I have introduced competitive programming and the concept of time complexity. The next few posts will talk about some other aspects of competitive programming – please stay tuned!

The next post can be found here

(Reference: Competitive Programmer’s Handbook by Antti Laaksonen)