### Execution time and big O

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