how many approx loops are allowed in 1 sec lime limit

general
,
1

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

5 Likes
2

it obviously depends on your cpu speed. the number you’re looking for is the invert of the frequency.

1 Like
3

@cyberax I was talking particularly about code chef ,how many approx loops are allowed by code chef online judge in 1 second

2 Likes
4

Hi, I answered once similar question on TopCoder forum (small modification here).

  • when N <= 10, then both O(N!) and O(2N) are ok (for 2N probably N <= 20 is ok too)
  • when N <= 100, then O(N3) is ok (I guess that N4 is also ok, but never tried)
  • when N <= 1.000, then N2 is also ok
  • when N <= 1.000.000, then O(N) is fine (I guess that 10.000.000 is fine too, but I never tried in contest)
  • finally when N = 1.000.000.000 then O(N) is NOT ok, you have to find something better…

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.

9 Likes
5

If we use number of If-else statements within a loop, would it affect the time complexity?

2 Likes
6

@harry1995

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.

7

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 time-out for even 10^6 operations/sec;

1 Like
8

thanks…:slight_smile:

9

np dear :slight_smile:

10

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.

long long i,j;
for(i=0;i<1e+8;i++)
j=i*i;

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 .

int i,j;
for(i=0;i<1e+8;i++)
j=sqrt(i);

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.

11

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.

1 Like