The following recursive algorithm returns the index of the smallest element in a list A containing n elements. The elements in the list are assumed to start from index # 1

findMin (startIndex, A) if startIndex = n // case of list containing one element return startIndex x = findmin (startIntex+1, A) // find min in elements index+1 .. n if A[x] < A[startIndex] // compare it with element at index return x // return the index of the smallest else return startIndex

Using the algorithm in above, write a recursive version for Selection Sort. For those who dont remember Selection Sort, below is the pseudocode for it. Note that the version below does not use the recursive findMin outlined in above. Then write a Recurrence Relation for the time complexity of your recursive selection sort algorithm you developed in c) above, then solve it to find its time complexity.

selSort (A) for i = 1 to n-1 minIndex = i // find the index of the min element between j and n for j = i+1 to n if A[j] < A [minIndex] minIndex = j swap (A[i], A[minIndex]) // swap the min element with the ith element