Reference no: EM131165906

Let A(1 : n) denote the elements in positions 1 to n of the array A. A recursive description of insertion sort is that to sort A(1 : n), first we sort A(1 : n-1), and then we insert A(n), by shifting the elements greater than A(n) each one place to the right and then inserting the original value of A(n) into the place we have opened up. If n = 1 we do nothing. Let Sj (A(1 : j)) be the time needed to sort the portion of A from place 1 to place j, and let Ij (A(1 : j), b) be the time needed to insert the element b into a sorted list originally in the first j positions of A to give a sorted list in the first j + 1 positions of A. Note that Sj and Ij depend on the actual array A, and not just on the value of j. Use Sj and Ij to describe the time needed to use insertion sort to sort A(1 : n) in terms of the time needed to sort A(1 : n - 1). Don't forget that it is necessary to copy the element in position i of A into a variable b before moving elements of A(1 : i-1) to the right to make a place for it, because this moving process will write over A(i). Let T(n) be the expected value of Sn; that is, the expected running time of insertion sort on a list of n items. Write a recurrence for T(n) in terms of T(n-1) by taking expected values in the equation that corresponds to your previous description of the time needed to use insertion sort on a particular array. Solve your recurrence relation in big-Θ terms.