CODEWITHSUNDEEP
javaalgorithmbig-oanalysisexecution
John Wozniak
John Wozniak

Reputation: 9

Execution time and big O

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

Upvotes: 0

Views: 1162

Answers (2)

Jarosław Gomułka
Jarosław Gomułka

Reputation: 4995

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

Upvotes: 7

xikkub
xikkub

Reputation: 1660

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.

Upvotes: 0

Related Questions