Consider the following sorting algorithm:

$1$: func SELECTION$-$SORT$($arr$)$: $2$: $,n=$ LEN $(arr)3$: $,$ if $n1$: $4$: $,$ return arr $5$: $,$ else: $6$: $,$ result $=$ SELECTION$-$SORT $(arr[0$:$n-1]),$ Sort all but the last element $7$: $,$ last$-$element $=$arr$[n-1]$

$1$

$8$: $,$ let $i$ be the first index such that arr$[i-1]$ last$-$element $$arr$[i]$

$9$: result.INSERT$($last$-$element, $i)$ Insert last$-$element into correct position

$10$: return result

Prove the correctness of this algorithm by induction.

Write a recurrence, $T(n),$ for the runtime of this algorithm. Assume finding $i$ in line $8$ is done via linear search.

Solve this recurrence in terms of asymptotic complexity, i$.$e$.,$ find a function $f(n)$ such that $T(n)=O(f(n)).$

How does this recurrence change if we find i via binary search? How does this affect the asymptotic complexity?