how many approx loops are allowed in 1 sec lime limit? I somewhere read that it is approx 10million loops for 1 second.if I am wrong please correct me. Thanks in advance asked 06 Jul '12, 20:22

Number of iterations allowed for each range of n : 1.n=10^5 most used constraint in competitve programming , three types of complexity is allowed in these type of questions . fist O(n) ,O(nlogn) and O(nrootn) , you have to use fast io in O(nrootn) complexity. 2.n=10^6 only two types of complexity is allowed here, first O(n) and O(nlogn). 3.n>=10^9 you can use maximum of O(logn) complexity. 4.n=10^3 these kinds of questions requires O(n), O(n^2) or O(n^2logn) complexity. 5.n=10^2 you can use O(n), O(n^2), O(n^2logn), O(n^3) orO(n^3logn) complexity. 6.n<=20  These question requires exponential complexity. mostly bitmasking questions are given in these ranges of n. So basically use can use maximum of 10^8 iterations , but if you are using above 10^7 iterations make sure you io method is fast,sometimes simple io doesn't fit in time limit. and obviously O(1) works for all kind of constraints. Hope it helps. answered 14 Feb '17, 10:48

Firsty, Number of iterations that can occur in one second is different for different languages . For e.g. The number of iterations that can occur in one second in C++ is much more than that in Python.. Plus, the time reqd also depends upon what is happening in those iterations .. Try to execute these codes in C++ to see the difference for yourself. 1. long long i,j; for(i=0;i<1e+8;i++) j=i*i; 2. long long i,j; for(i=0;i<1e+8;i++) j=sqrt(i) Since squareroot is costly operation, it is going to take a longer time to execute. Further, it also depends upon which data type you are working . 1. int i,j; for(i=0;i<1e+8;i++) j=sqrt(i); 2. long long i,j; for(i=0;i<1e+8;i++) j=sqrt(i) Even thought the above two are doing similar operations, the time required to work on int will be shorter than long long int. Try to implement the above codes in the codechef IDE and experiment with them to see for yourself. Thats the reason you don't declare long long int unless its necessary. And you use bool array if all its element are either 1 or 0. answered 13 Feb '17, 11:00

Every online judges have different time limits depending upon their server.So u can't assume it as 10 million loops/sec..U can see in some cases where the test cases even pass for 10^7 also and in some cases it will timeout for even 10^6 operations/sec; answered 12 Feb '17, 16:28

No, if else do not affect it significantly. In most of cases, it wont make any difference.. What is more important, is the number of times the loop is getting executed. answered 12 Feb '17, 12:20

If we use number of Ifelse statements within a loop, would it affect the time complexity? answered 12 Feb '17, 11:59

Hi, I answered once similar question on TopCoder forum (small modification here).
But it also depends what are you doing in the loop. For example you have to know how are data structures, you are using, implemented  when you are inserting into map in C++ such operation is O(log(n)) (where n is map size), so for loop with 10.000.000 inserts to map, you will get time limit probably. Also be aware that on TopCoder you are NOT reading input, you simply get it as method parameter and here it is consuming your time, especially when you use something else than C/C++ (Java, Python that's serious problem), that's why I assumed that you can do 100.000.000 operations per second, on CodeChef I would expect that max is 10.000.000. answered 08 Jul '12, 20:44

it obviously depends on your cpu speed. the number you're looking for is the invert of the frequency. answered 06 Jul '12, 22:37
3
@cyberax I was talking particularly about code chef ,how many approx loops are allowed by code chef online judge in 1 second
(07 Jul '12, 07:29)
