Time complexity of Test cases included with my program

In CodeChef, test cases are typically used with the while(t- -) loop. Let’s assume that the given constraints are:

1 <= t <= 10^2

1 <= n <= 10^4

If I have written a program with a time complexity of O(n^2), will the test cases affect my program’s time complexity? Specifically, will it be O(t * worst case of my individual test case)? If this is the case, it can heavily impact my program and cause it to exceed the time limit (TLE).
I came across this few weeks ago

If not, is it optimized by the problem setter to ensure that my program doesn’t receive a TLE for each individual test case?

  • Yes,it effects
  • No, it doesn’t effects
  • I am not sure about it

0 voters

Or further explain me in detail please.

1 Like

Hey @abhaypandey114 ,
Usually in most of the problems, you will find a line like The sum of N over all the test cases won't exceed 10^5 in the constraints section of the problem.

That 10^5 is the number you have to write your code for. If it is 10^5 then O(nlogn) type solution will work. If it is higher then better complexity will be required.

Is that mean , I dont have to worry for TLE, if individualy my program don’t exceed constraint’s for "the sum of N over all the test cases won’t exceed 10^5 .


Thank you very much. :melting_face: :melting_face: