Competitive Programming & Time Complexity

As Wikipedia says, competitive programming is a mind sport usually held over the Internet or a local network, involving participants trying to program according to provided specifications.

In other words, competitive programming is a type of contest where a number of programmers attempt to solve programming questions in a limited amount of time.

You can write your solution in any programming language that you’re comfortable with, and your solutions are judged by online judges. Solutions should pass all of the test cases (given and hidden) in order to be accepted under certain time and space limits.

You can do competitive programming in any programming language — C/C++, Java, and Python are highly recommended. Learn about all the syntaxes, built-in functions, templates, snippets, and library functions such as STL in C++, Big Integers in Java, etc. Working with the fundamentals will bring long term benefit to any individual. Before you start writing code, you should make sure you write code efficiently in the language you choose.

How do I get started with competitive programming? Is there a roadmap or a guide for competitive programming?

1. Choose the suitable programming language
2. Choose the powerful code editor
3. Learn basic data structures and algorithm concepts
4. Solving different problems

Approach for solving algorithms for competitive programming

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

• The problem statement — Always give yourself enough time to read the problem statement, carefully. Don’t be in a hurry, when you are reading the problem because this may result in the wrong interpretation of the problem and as a result of this, you will write the wrong code.

Remember, 40% of the problem is already solved by merely understanding the statement carefully.

• Input and output values, and the format in which they will be input/output — Always take input in the given format, and never use your own format. If you are not following it, then you will get the wrong answer instead of having the right code.
• Constraints on the input size — Before writing the code, you should look for the input/output constraints given in the question. This will help you in deciding the time complexity of your code so that you need not change the code again and again if the code is not in accordance with the constraints (then you will get the TLE error).
• 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. On the other hand, Implementation, requires knowing and understanding a programming language.

A lot of big tech companies, like Facebook and Google, hire through competitive programming competitions. As an added bonus, various online competitions offer some amazing prizes for the winners.

There are many considerations of the efficient coding. One of them is Time Complexity. Let’s get into them in detail.

Time Complexity

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 below loop, the number of iterations in loop is linear to ’n’ times. So time complexity is O(n)

for(int index=0;index<n;index++){
System.out.println(index);
}

On Nested loops, time complexity is O(n²). the print statements executes n² times

for(int index=0;index<n;index++){
for(int newIndex=0;newIndex<n;newIndex++){
System.out.println(index);
}

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

Let’s say we can compute the square sum of 3 numbers. As you can see, each statement is a basic operation (math and assignment). Each line takes constant time O(1). If we add up all statements’ time it will still be O(1). It doesn’t matter if the numbers are 0or 9,007,199,254,740,991, it will perform the same number of operations.

function squareSum(a, b, c) {
const sa = a * a;
const sb = b * b;
const sc = c * c;
const sum = sa + sb + sc;
return sum;
}

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²).

Be careful with function calls. You will have to go to the implementation and check their run time. More on that later.

Types Of Time Complexity

1. Best Time Complexity: Define the input for which algorithm takes less time or minimum time. In the best case calculate the lower bound of an algorithm. Example: In the linear search when search data is present at the first location of large data then the best case occurs.
2. Average Time Complexity: In the average case take all random inputs and calculate the computation time for all inputs.
   And then we divide it by the total number of inputs.
3. Worst Time Complexity: Define the input for which algorithm takes a long time or maximum time. In the worst calculate the upper bound of an algorithm. Example: In the linear search when search data is present at the last location of large data then the worst case occurs.

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:

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!

Now, your turn!

Thanks for reading this far. Here are some things you can do next:

• Got questions? comment below.
• Was it useful? Show your support and share it.