You are not logged in. Please login at www.codechef.com to post your questions!

×

how many approx loops are allowed in 1 sec lime limit

5
3

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

raman92's gravatar image

1★raman92
2044815
accept rate: 0%


-1

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

link

answered 06 Jul '12, 22:37

cyberax's gravatar image

2★cyberax ♦
3.4k21955
accept rate: 20%

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) raman921★

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.

link

answered 08 Jul '12, 20:44

betlista's gravatar image

3★betlista ♦♦
16.8k49115225
accept rate: 11%

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

link

answered 12 Feb, 11:59

harry1995's gravatar image

3★harry1995
2924
accept rate: 5%

thanks...:)

(12 Feb, 16:50) harry19953★

np dear :)

(12 Feb, 18:39) vijju123 ♦4★

@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.

link

answered 12 Feb, 12:20

vijju123's gravatar image

4★vijju123 ♦
11.3k1316
accept rate: 18%

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;

link

answered 12 Feb, 16:28

kashyap2108's gravatar image

1★kashyap2108
1114
accept rate: 0%

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.

link

answered 13 Feb, 11:00

pankajkhan's gravatar image

5★pankajkhan
1.0k9
accept rate: 13%

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.

link

answered 14 Feb, 10:48

lashavi's gravatar image

4★lashavi
863
accept rate: 12%

edited 14 Feb, 10:58

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×214
×108

question asked: 06 Jul '12, 20:22

question was seen: 17,599 times

last updated: 14 Feb, 10:58