×

# how many approx loops are allowed in 2.5 sec time limit

 2 How many approx loops can be traversed in 2.5 sec? And what should be best complexity to traverse 10^6? asked 12 Aug '18, 18:57 2★ezio27 31●6 accept rate: 0%

 2 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, answered 12 Aug '18, 19:55 851●1●1●8 accept rate: 13% Thanks this is helpful. (13 Aug '18, 02:21) ezio272★
 2 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. answered 12 Aug '18, 19:56 246●1●8 accept rate: 5%
 1 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! answered 12 Aug '18, 19:05 124●5 accept rate: 7% 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? (12 Aug '18, 19:10) ezio272★ I would say somewhere around 10^4 elements. (12 Aug '18, 20:18)
 0 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 : ) answered 04 Oct '18, 01:25 359●6 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×678
×263
×204
×141

question asked: 12 Aug '18, 18:57

question was seen: 1,248 times

last updated: 04 Oct '18, 01:25