I would like to know the no of operations/computations(TRIVIAL computations nothing complex) in 1 second in JAVA.
I am asking for CODECHEF ,TOPCODER ,SPOJ,etc
Plz tell this especially bansal1232
1)in 1 second 10^8 executions possible max for codechef/spoj/topcoder using java
2)if on problem’s page if the question says 1 second then the time limit for me is 1 second only ,even if i use java
plz tell which statement is correct /incorrect by pointing 2 them ,like say statement 1 is correct/incorrect nd then the explanation why incorrect
2 Likes
i think it depends upon the hardware of the system CPU,RAM
Usually Time limit in java is given by 2 * X (Where is X is time given in problem setter page) in codechef online judge.
According to any one! In one second, you can only perform 10^7 instruction but if you running upto 10^8 then this would be considered as a border case. But if it is going upto 10^9 then it must give TLE according to the server configuration of any platfrom!
To know more about this, You can refer this Article
Codechef time limit configuration Click here
3 Likes
I am curious that why do you want to know this number? Complexity and predictions of if the code will get a TLE are actually easy if we look at constraints (excuse the border cases!)
Like, if size of array is in 10^9 then O(n2), O(n3) etc type algos will definitely fail.
However, if what u wanted to know was time allotted for the language, then bansal gave a very nice answer. (would had upvoted if I could…XD :_( )
In case of hardware, operation a second vary from machine to machine, and in case of online IDE like codechef, you need to check out in FAQ!
2 Likes
Hi vaibhavchhabra,
no of computations in 1 sec is actually a frequency of processor (in giga/mega hz) depends on hardware but if you want to know about codechef/spoj or other competitive programming sites then for java it is around 5 * 10^7 instructions but no. of instructions does not guaranteed to be same because type of instructions also matters. Sometimes it varies problem to problem because no. of operations inside loop and function call everything counts. While solving problems a good approach is necessary because problem is set while keeping in mind everything so for competitive programming approx (5*10^7) is enough.
if you want to check time for different machines then you can simply use System.currentTimeMillis() to get time in millisecond and subtract this value to get interval time in millisecond.
if anything is not clear to you please comment.
So in Java(Codechef/SPOJ/TOPCODER) ,
In 1 second 10^8 instructions can be executed max?
Lets say in a probem the time limit is 1 second given on the problem page ,so since i am using java so i can perform 2*10^8 operations and my time limit is 2 seconds right ?
So in Java(Codechef/SPOJ/TOPCODER) ,
In 1 second 10^8 instructions can be executed max?
Lets say in a probem the time limit is 1 second given on the problem page ,so since i am using java so i can perform 2*10^8 operations and my time limit is 2 seconds right ?
QUESTION UPDATED PLEASE SEE THE QUESTION AGAIN
1 Like
NO it doesn’t sound like that! You still need to perform upto consideration of 1sec because javac compiler of java takes plenty of parsing time as compare to C/C++. So Online judge will automatically eradicate this issue
So u mean 2 say
1)in 1 second 10^8 executions possible max for codechef/spoj/topcoder using java
2)if on problem’s page if the question says one second then the time limit for me is 1 second only even if i use java
bansal plz tell which statement is correct /incorrect by pointing 2 them like say statement 1 is correct/incorrect nd then the explanation
Java executes 5 * 10^7 operations approx in 1second. The time limit shown in the problem statement is for c & c++(1 sec) means java get 2 times than c++ which is 2 second. Because java is slower than c++. note that this includes compilation + execution.
Like python and ruby etc. user get 5 seconds but that is not benefit because these language require 5 times time than c++.
Finally you can execute 2 * 5 * 10^7 operations if time limit is 1 second.
Time limit for java is always 2 times of c++ unless time limit for java is explicitly specified.
Please dont be so precise no. Of operations in 1 sec varies from 10^6 to 10^8 depends on type of instruction thats why i told you average i.e. 5* 10^7.
Some problems need same amount of time in c++ and java due to type of operation and resources etc. Thats why time limit is same for those problems. Like ICPC world final problems have same time limit for c c++ java and python. It doesn’t mean running time is exactly same for all languages but nearly same.
I think you got now? If not then comment.
Look at my comment below.
Don’t think it in terms of operations, they vary a lot depending on thy type , even when all are trivial operations.Like addition is faster than say decimal division, although we consider both constant time.
Instead look at it this way, when you want to check whether the complexity that you get is the best, just get the number of iterations your loop will make(handle nested loops accordingly) and multiply that to the complexity of the function you do within those loops.
For example(in Java):
for(int i = 0 ; i < 10^5 ; i++){
for(int j = 0 ;j < 10^2 ; j++ ){
set[i].add( arr[j] ) // arr is some array and set is an array of set
}
}
Here, since the complexity of adding an element to a set is O(log n), therefor total complexity will be O(10^5 * 10^2 * log(10^510^2)). If this is lesser than or about equal to 10^8, you are fine to go.
In this case it will be, as log(10^7) is approx ~ 20, so #computations = 10^7 * log 10^7=210^8, which should run.
Remember, in most cases, the loop constraints will be dependent on various other things , so the loop probably wont run this many time in any scenario, so this method should be fine for calculating the complexity and the gross number of operations.
This sort of malpractice was not expected here. You two have been reported.
Allright I got that thanks