Question 2 [20 marks] a. [10 marks] To sort an array 4[1: n] containing n integers, we can recursively sort the subarray A[1:n-1] and then insert A[n] into the sorted subarray A[1:n-1]. The pseudocode for a recursive insertion sort algorithm is given below. RecursiveInsertionSort(4, n) if n> 1 then RecursiveInsertionSort(4, n-1) x=A[n] j-n-1 while > 0 and A[]>x do AU+1]-AU] j-j-1 Aj+1]-x Give the recurrence relation for the worst-case running time of the recursive insertion sort algorithm and solve the recurrence by the backward substitution method.