Search code examples
javaalgorithmbig-oanalysisexecution

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.


Solution

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