How to overcome Time Limit Exceed(TLE)?

Many programmers always argue that the problems in Competitive Programming always end up with TLE(Time Limit Exceed). The main problem with this error is that it will not allow you to know that your solution would reach to correct solution or not! 
 

Why TLE comes?

• Online Judge Restrictions: TLE comes because the Online judge has some restriction that it will not allow to process the instruction after a certain Time limit given by Problem setter the problem(1 sec).
• Server Configuration: The exact time taken by the code depends on the speed of the server, the architecture of the server, OS, and certainly on the complexity of the algorithm. So different servers like practice, CodeChef, SPOJ, etc., may have different execution speeds. By estimating the maximum value of N (N is the total number of instructions of your whole code), you can roughly estimate the TLE would occur or not in 1 sec. 
   

MAX value of N                       Time complexity
   10^9                              O(logN) or Sqrt(N)
   10^8                              O(N) Border case
   10^7                              O(N) Might be accepted
   10^6                              O(N) Perfect
   10^5                              O(N * logN)
   10^4                              O(N ^ 2)
   10^2                              O(N ^ 3)
   <= 160                            O(N ^ 4)
   <= 18                             O(2N*N2) 
   <= 10                             O(N!), O(2N)

• So after analyzing this chart you can roughly estimate your Time complexity and make your code within the upper bound limit.
• Method of reading input and writing output is too slow: Sometimes, the methods used by a programmer for input-output may cause TLE.

Overcome Time Limit Errors

• Change methods of Input-Output: You must choose proper input-output functions and data structure that would help you in optimization. 
  • In C++, do not use cin/cout – use scanf and printf instead.
  • In Java, do not use a Scanner – use a BufferedReader instead.
• Bounds of loops may be reduced: Read the bounds in the input carefully before writing your program, and try to figure out which inputs will cause your program to run slower. For example, if a problem tells you that N <= 100000 or N<=1000000, and your program has nested loops each which go up to N, your program will never be fast enough.
• Optimize your Algorithm: If nothing works after all this, then you should try changing the algorithm or the approach you are using to solve your problem. Generally, the internal test cases are designed in such a way that you will be able to clear all of them only if you choose the best possible algorithm.
• Look for Suggestions given: Although this should be the last step, you must look at the comments given below, any problem in which other programmers might have given a hint on how the problem can be solved better and more efficiently hinted at. And even when you overcome TLE try more exhaustive and corner test cases against your program to check the performance.

Ultimately, with experience, you’ll surely come to know what to do and what not to avoid TLEs. The more you code the more you get to know about how to compete for TLE. 

Practice Now 

This article is contributed by Shubham Bansal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks. 

Please write comments if you find anything incorrect, or have more information about the topic discussed above.