Question $3(15\mathrm{.}0$ marks$)$

Recursion

Insertion sort can also be expressed as a recursive procedure as well: In order to sort

$,$ we recursively sort $A[1..n-1]$ and insert $A[n]$ into the sorted array $A[1..n-1].$

The pseudocode of an insertion sort algorithm implemented using recursion is as follow:

$($i$)$ Let $T(n)$ be the running time of the recursively written Insert sort on an array of

size n $.$ Write the recurrence equation that describes the running time of

insertionSortR$($int $|$~$A,$ int $n).$

$(5\mathrm{.}0$ marks$)$

$($ii$)$ Solve the recurrence equation $T(n)$ to determine the upper bound complexity of

the recursive Insertion sort implemented in part $($i$).$