We'll now dry run our algorithm on the input array and trace the number of instructions executed in each iteration. We'll sum up the number of instructions across all the iterations to get a final count of instructions for the entire run. In the previous section, we worked out the instruction counts of the inner and outer loop to be those below:

Number of instructions executed per iteration of outer for loop = 4
Number of instructions executed per iteration of inner while loop = 7

The code from the previous section is reproduced below:

1.         for (int i = 0; i < input.length; i++) {
2.             int key = input[i];
3.             j = i - 1;
4.             while (j >= 0 && input[j] > key) {
5.                 if (input[j] > key) {
6.                     int tmp = input[j];
7.                     input[j] = key;
8.                     input[j + 1] = tmp;
9.                     j--;
10.                 }
11.            }
12.        }

First Iteration of Outer Loop | when i = 0, key = 7

j = -1 inner loop doesn't execute

%0 node_1 7 node_1537433179208 6 node_1537433255028 5 node_1537433254832 4 node_1537433245823 3

Total cost for 1st iteration = Outer Loop + Inner Loop
= 4 + [ ( iterations * 7 ) + 2 ]
= 4 + [ ( 0 * 7 ) + 2 ]
= 6 instructions

Second Iteration of Outer Loop | when i = 1, key = 6

j = 0

%0 node_1 6 node_2 7 node_3 5 node_1537405566372 4 node_1537405606971 3

Total cost for 2nd iteration = Outer Loop + Inner Loop
= 4 + [ ( iterations * 7 ) + 2 ]
= 4 + [ ( 1 * 7 ) + 2 ]
= 13 instructions

Third Iteration of Outer Loop | when i = 2, key = 5

j = 1

%0 node_1 6 node_2 5 node_3 7 node_1537406031517 4 node_1537406005114 3

j = 0

%0 node_1 5 node_2 6 node_3 7 node_1537406193247 4 node_1537406143492 3

Total cost for 3rd iteration = Outer Loop + Inner Loop
= 4 + [ ( iterations * 7 ) + 2 ]
= 4 + [ ( 2 * 7 ) + 2 ]
= 20 instructions

Fourth Iteration of Outer Loop | when i = 3, key = 4

j = 2

%0 node_1 5 node_2 6 node_3 4 node_1537406791522 7 node_1537406771595 3

j = 1

%0 node_1 5 node_2 4 node_3 6 node_1537406866719 7 node_1537406862420 3

j = 0

%0 node_1 4 node_1537407038135 5 node_1537407013928 6 node_1537407014301 7 node_1537407076377 3

Total cost for 1st iteration = Outer Loop + Inner Loop
= 4 + [ ( iterations * 7 ) + 2 ]
= 4 + [ ( 3 * 7 ) + 2 ]
= 27 instructions

Fifth Iteration of Outer Loop | when i = 4, key = 3

j=3

%0 node_3 4 node_1537433422315 5 node_1537433373043 6 node_1537433415343 3 node_1537433451879 7

j=2

%0 node_1 4 node_1537433796889 5 node_1537433803259 3 node_1537433750869 6 node_1537433780668 7

j=1

%0 node_1 4 node_1537433867992 3 node_1537433887211 5 node_1537433863909 6 node_1537433886261 7

j=0

%0 node_1 3 node_1537433879326 4 node_1537433936354 5 node_1537433873099 6 node_1537433954276 7

Total cost for 1st iteration = Outer Loop + Inner Loop
= 4 + [ ( iterations * 7 ) + 2 ]
= 4 + [ ( 4 * 7 ) + 2 ]
= 34 instructions

However, remember that to exit the loop the increment and the inequality statements will execute for one last time, so we need to add that cost too.
= 34 + 2
= 36 instructions

IterationInstructions Executed
16
213
320
427
536
Total Cost6 + 13 + 20 + 27 + 36 = 102 instructions

One can observe that as the size of the array increases, the inner loop's iterations will correspondingly increase, and the running time of the program will increase.

Using Formulas

From the previous section, we can plug the formulas we produced to get the same result. There were 5 iterations of the outer for loop, so the instructions executed for the outer for loop are:

[2∗(n+1)+2n], where n is number of iterations[2*(n+1)+2n],\:where\:n\:is\:number\:of\:iterations

=[2∗(5+1)+2∗5]=[2*(5+1)+2*5]

=[12+10]=[12+10]

=22 instructions=22\:instructions

The number of iterations for the inner loop varies for each iteration of the outer loop given by (k x 7) + 2

  • No iteration on first run of outer loop.
    = (0 x 7) + 2 = 2
  • 1 iteration in second run of outer loop:
    = ( 1 x 7 ) + 2 = 9
  • 2 iterations on third run of outer loop:
    = ( 2 x 7 ) + 2 = 16
  • 3 iterations on fourth run of outer loop:
    = ( 3 x 7 ) + 2= 23
  • 4 iterations on fifth run of outer loop:
    = ( 4 x 7 ) + 2= 30
  • Total instructions executed for the inner while loop are then: 2 + 9 + 16 + 23 + 30 = 80 instructions.

The number of instructions for the entire run comes out to be 80 + 22 = 102 instructions. Note how our formulas match the exact count we found from the dry run!