What should be the worst case time complexity of code to pass in 3 sec on Codechef?

complexity
time-limit

#1

I am trying to solve a question whose overall time limit is 3 sec. It has three subtasks. Time limit for each sub tasks in not mentioned, only overall time limit is given. So my first question is Does different subtasks have different time limit?

If the answer to the above question is NO then What should be the worst case time complexity of code to pass in 3 sec on Codechef including test cases?

Like 10^6, 10^7, 10^8 or 10^9?


#2

@ishpreet At codechef, usually time limit for each subtasks is same and is equal to the overall time limit of question and approximately you can perform 10$^8$ to 10$^9$ computations per second, which means for a question having time limit 3s, you can perform approximately 3*10^8 to $3*10^9$computations.


#3

Actually, it depends on problem setter, and its most likely, each sub-task has got different time limit and the last sub-task with original constraint has TL of 3 sec.

Runtime Analysis


#4

@ishpreet if you got your answer then please help me too. I am also stuck, all test cases where n<10^6 are accepted but for N>=10^6 I am getting TLE.


#5

Thanks @srd091. But my code complexity is 6*10^8. I got TLE. Don’t Know Why?


#6

@vpriyanshu40 What’s the time complexity of your code and What’s the time limit?