How to decide “Time Complexity” for your coding problem ?

Kshitiz Bansal
3 min readApr 11, 2021

--

I offer an immense pleasure for you showing up here. Being a computer science devotee proficient in Cloud Computing & Data Engineering, I have always looked forward in learning, sharing & gaining knowledge with overwhelming support of brilliant minds like you. With my deep regards, I hope this article will be able to reach out to the desire you wish to read ahead. Thankyou!

Kshitiz

If you have ever tried to solve a coding problem on any of the coding platforms, you must be relating to the image above in one way or so. The most common error we guys face during an attempt to crack a problem is that frustrating ‘Time Limit Exceeded’ or ‘TLE’ error. Even with so many modifications to what one can think to reduce it, I personally have faced a lot failures to this. Today we will understand the basic concept of time limit for a particular problem & how to avoid this error in the very first time.

The 10⁸ Operations Rule

This basic rule will be enough for a programmer to have a fair understanding of the algorithm which is to be implemented. The 10⁸ Operations Rule states that for any online judge of coding platform, your algorithm operations should not exceed 10⁸ times, which means that for a given range of input values, algorithm should be implemented in such a way that it will always perform < 10⁸ operations overall. Below is a sample chart for the above description which will help you understand better the statement of the rule:

Maximum valid time complexity for a given length range

Example

W.r.t to above chart, it is clear that if the input range is given around 100 for a complex problem, we have the privilege to design an algorithm taking up to 10⁴ operations at max. Similarly, say now if we have 10⁵ as the input range, we should be restricted to the boundary of algorithms taking not more than O(n * log(n)) operations. Following this strategy will not only avoid the occurrence of TLE, but will also help to have the application understanding of each algorithm we apply.

One keen observation you must have noticed from the above chart is that ‘Greater the input range, lesser should be the operations executed’. This concludes to the following graphical representation of the input-time relation in world of Algorithms.

Next time you put your hands on to write a code always make sure to follow this 10⁸ operations rule. At least the judge will not return that irritating TLE this time. I hope the above summary of entire concept must have given you an idea to decide the maximum level of complexity depth you can reach prior building a logic.

Thanks again for you to spending those precious couple of minutes of yours reading the article. For any query or suggestion please feel free to reach out:

--

--

Kshitiz Bansal
Kshitiz Bansal

No responses yet