Insertion sort can be expressed as a recurrence procedure. In order to sort A[1,2,....n] , we recursively sort A[1,2,....(n-1)] and then insert A[n] into the sorted array A[1,2,....(n-1)] . How will you write the running time of this recursive version of insertion sort.
\( public static int[] RecursiveInsertionSort(int[] array, int n) { |