Execution time and big O

Go To StackoverFlow.com

0

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

2012-04-03 21:22
by John Wozniak
I fear your prof is using "execution time" in some rather peculiar manner. You'll have to look up the definition for that one yourself, I doubt it's standard terminology. - Voo 2012-04-03 21:28
I think it's abstracted. Consider n some multiple of seconds, and then you can convert the formula into 'time.' This would, of course, depend on the clock speed of the machine where the code is executing - ingyhere 2012-04-03 21:31
It's way too abstract, SomeJavaStatement could be much more complex than i++cxyzs7 2012-04-03 21:33
Agreed. To make sense it should define SomeJavaStatement as an operation of O(1). There was probably some definition left out of the question here for brevity's sake - ingyhere 2012-04-03 21:36
@ingyhere Even then, that has absolutely nothing to do with the execution time (add is a good bit cheaper than mul on most CPUs), but just the number of statements. Ah wel - Voo 2012-04-03 22:12
@Voo SomeJavaStatement is singular, meaning one operation. I don't think it refers to a method call. ... But I get what you're saying - ingyhere 2012-04-03 23:24
@ingyhere Well 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


7

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 :)

2012-04-03 21:29
by Jarosław Gomułka
You're talking about the variable 'i' in the comment next to 'j' looping - ingyhere 2012-04-03 23:22


0

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.

2012-04-03 21:34
by collinjsimpson