how many approx loops are allowed in 2.5 sec time limit

general
, , ,
1

How many approx loops can be traversed in 2.5 sec? And what should be best complexity to traverse 10^6?

2 Likes
2

Considering that the CPU does approximately 10^9 operations per second, a complexity of n^2 would be more than the time bound.

I would assume the solution to be either O(n) or O(n log n) to fit within the time bound. It can be even lesser.

The number of loops is a tricky question, depending on on what elements it is traversing. But if the total operations in all loops you have used is closer to 10^8, you should be good. All the best!

1 Like
3

Thanks you so much. Would you please tell me if i am using n^2 worst case complexity what will be max i can traverse in 2.5 sec?

4

This question has already been asked multiple times at Codechef(page1, page2) and Codeforces(page1) blogs where a beautiful chart is available where you can refer. For the current codechef judge, with 10^6 limit, expect the complexity would be O(n), O(nlogn), or \theta(nlogn). . .

But again, you have to consider what exactly are you trying to do inside the loops. For example, if you simply run two for loops where each loop runs for 10^9 times, so overall 10^18 times, you will be amazed how fast the codechef judge completes this loops, which is almost in no time. This is because you are doing nothing inside the loop and the compiler has actually removed those loops from the code path. However, obviously, why will you have empty loops at Codechef, which is why the above-suggested links would give rough estimates.

Best Regards,

2 Likes
5

On most online judges, the number of operations is 10^8 per second. This limit is for C++. For other languages, it may be slower. In 2.5 seconds, an n^2 solution with n = 10000 might just pass, if the number of computations inside the loops isn’t too much.

1 Like
6

I would say somewhere around 10^4 elements.

7

Thanks this is helpful.

8

as already said 10^8 number of operations per second(not 10^8 times the loop) is the limit for online judge

as an example if your loops run say 10^7 times but you are perfoming 15 operations per loop then effectively you are doing 1.5*10^8 operations which may be a TLE

so what I want to say is that 10^8 operations are allowed not 10^8 times the loop

hope u get a clear thought : )