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


how many approx loops are allowed in 1 sec lime limit


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

accept rate: 0%


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

cyberax's gravatar image

2★cyberax ♦
accept rate: 20%


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


answered 08 Jul '12, 20:44

betlista's gravatar image

3★betlista ♦♦
accept rate: 11%

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


answered 12 Feb, 11:59

harry1995's gravatar image

accept rate: 5%


(12 Feb, 16:50) harry19953★

np dear :)

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


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, 12:20

vijju123's gravatar image

4★vijju123 ♦
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;


answered 12 Feb, 16:28

kashyap2108's gravatar image

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.


answered 13 Feb, 11:00

pankajkhan's gravatar image

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.


answered 14 Feb, 10:48

lashavi's gravatar image

accept rate: 12%

edited 14 Feb, 10:58

toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 06 Jul '12, 20:22

question was seen: 17,599 times

last updated: 14 Feb, 10:58