(Before anyone says anything Yes this was homework but i have already turned it in and have gotten it back, i just want to figure this out for the test tomorrow.)
The problem was to calculate the execution times and big O for the code snippet. I can calculate the big O fine, but i dont get how you can determine the execution time. Ok basically what i dont understand is how to calculate the execution time
for(i=0; i < n; i++){
SomeJavaStatment;
for(j=0; j < 2 * n; J+= 2){
SomeJavaStatment;
SomeJavaStatment;
}
}
the correct answer was Big O(n^2) I got that right however I had no idea what the execution time was, and the correct answer for that was 4n^2+5n+2.
I would appreciate if someone could explain how i would go about getting to that answer.
SomeJavaStatement
could be much more complex than i++
cxyzs7 2012-04-03 21:33
statement
is an exactly defined token in the JLS and even more general statement
is quite usual in grammars and has a specific meaning (you can look it up in $18 of the JLS). {foo(); bar(); baz();}
is a single statement for example. Apart from that the simple fact is, that mul eax, ebx
is about 3times as expensive as add eax, ebx
on modern x86 CPUs. Hence such generalizations are completely useless anyhow. If I were the student I'd go complain (ok no, I wouldn't - lazyness and all - Voo 2012-04-03 23:29
I don't think, that execution time should be determined that way but:
//assignment to i takes 1 operation
for(i=0; i < n; i++){ // i++ is executed n times, i < n is executed (n+1) times
SomeJavaStatment; // n times
//assignment to j takes 1 operation
for(j=0; j < 2 * n; j+= 2){ // j+=2 is executed n*n times, j < 2*n is executed n*(n+1) times
SomeJavaStatment; // n * n times
SomeJavaStatment; // n * n times
}
}
In total it gives 1 + n + (n+1) + n + n + (n*n) + (n+1)*n + (n*n) + (n*n) = 4 * n^2 + 5*n + 2
:)
Big O describes the upper bound of a function. Your function is not only Big O(n^2), but it also has tight bounds (for any given value of n
, the function has the exact same runtime). You can manually calculate the exact tight bound, or you can express it as a summation resulting in 4n^2+5n+2
.