2. (25 points) consider the following procedure acting on an array a[1: : n]. insertion sort(a[1: : n]) cost times 1. for j 2 to n c1 2. key a[ j] c2 3. i c3 4. while i > 0 and a[i] > key c4 5. a[i+1] a[i] c5 6. i c6 7. a[i+1] key c7 (a) let t j denote the number of times the while loop test in line 4 is executed for that value of j. fill in for each line of instruction, the number of times the instruction is executed. (b) derive the expression for the running time of insertion sort in terms of n, ci, and t j. (c) what is t j for the best-case scenario, i. e., when the running time of the algorithm is the smallest. use that to derive the expression for the best-case running time of insertion sort in terms of n and ci. what is the best-case time complexity of insertion sort using the big-o notation? (d) what is t j for the worst-case scenario, i. e., when the running time of the algorithm is the largest. use that to derive the expression for the worst-case running time of insertion sort in terms of n and ci. what is the worst-case time complexity of insertion sort using the big-o notation?