Problem $5.$ Selection Sort $(10$ points$)$

Below is the pseudocode for Selection Sort, a cousin of Insertion Sort.

Selection Sort can also be implemented in a recursive way, where we $($iteratively$)$ find the minimum

element and place it in position $A[i],$ then recursively sort $A[i+1$dots.$n].$

$($a$)$ Write the pseudocode for recursive Selection Sort

Solution:

$($b$)$ Compute the worst$-$case run$-$time $T(n)$ of your algorithm, assuming it's called for the first

time with $i=1.$ Show all your steps. $($Remember to include the base case!$)$

Solution:

$($c$)$ Solve your recurrence and give a tight$-$bound on your recursive Selection Sort run$-$time $($using

any method to solve that you like$).$ You're welcome to simplify your recurrence by dropping

constants.

Solution: