1. (6 points) The following pseudo code shows an implementation of the selection sort algorithm. 1:...

  

Transcribed Image Text:

1. (6 points) The following pseudo code shows an implementation of the selection sort algorithm. 1: function SELECTION-SORT(A, n) for = 1 to n-1 do mini if A[j] < A[min] then minj 2: 3: 4: for j = i+1 ton do 5: 6: 7: 8: 9: 10: end if end for swap A[i], A[min] end for 11: end function (a) Compute the worst case running time using the method shown in class for insertion sort. That is, assign a different constant to each of the lines 2-10 and use them to compute the running time. (b) Repeat part (a) for the best case running time. (c) Use the O-notation to compare the worst-case and best-case running times computed above to the following functions n, nlgn, and n. (d) Compare the worst and best case running times of the selection sort to the corresponding times of the insertion sort using one of the three notations, , o, or w. 1. (6 points) The following pseudo code shows an implementation of the selection sort algorithm. 1: function SELECTION-SORT(A, n) for = 1 to n-1 do mini if A[j] < A[min] then minj 2: 3: 4: for j = i+1 ton do 5: 6: 7: 8: 9: 10: end if end for swap A[i], A[min] end for 11: end function (a) Compute the worst case running time using the method shown in class for insertion sort. That is, assign a different constant to each of the lines 2-10 and use them to compute the running time. (b) Repeat part (a) for the best case running time. (c) Use the O-notation to compare the worst-case and best-case running times computed above to the following functions n, nlgn, and n. (d) Compare the worst and best case running times of the selection sort to the corresponding times of the insertion sort using one of the three notations, , o, or w.