Analyzing Algorithms Part III

Generalizing Instruction Count

Let's try to generalize the running time for an array of size n.

Code Statement	Cost
1.    for (int i = 0; i < input.length; i++) {	executed (2 x n) + 2 times.
2.        int key = input[i];	executed n times
3.        int j = i - 1;	executed n times
4.        while (j >= 0 && input[j] > key) {	We already calculated the cost of each iteration of the inner loop. We sum up the costs across all the iterations. Note that the inner loop will be executed n times and each execution will result in (iterations x 7)+2 instructions being executed. And the number of iterations will successively increase from 0, 1, 2 all the way up to(n-1). See the dry run in the previous lesson to convince yourself of the validity of this result.
5.             Inner loop statments	[(0 x 7) + 2] + [(1 x 7) + 2] + [(2 x 7) + 2] + ... [( (n-1) x 7) + 2] = 2n + 7 * [ 0 + 1 + 2 + ... (n-1) ] = 2n + 7 [ n(n-1)⁄2 ]
11.        }  //inner loop ends
12.   }

If we use the above formulas and apply an array of size 5 to them, then the cost should match with what we calculated earlier.

$$Total\:Cost=Outer\:loop\:instructions + Inner\:loop\:instructions$$

$$=[2*(n+1)+2n]+[2n+7[\frac{n*(n-1)}{2}]]$$

$$=[2*(5+1)+10]+[10+7[\frac{5*(5-1)}{2}]]$$ ...