Recursive version of Insertion Sort basicsorting sorting recursion insertionsort timecomplexity array    Posted: 5 years ago Updated: 4 years ago Edit answers (1) views (25765)

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.

 Posted: 5 years ago 1 0 Edit $$T(n)=\left\{\begin{array}{ll} O(1) & \mbox{if n = 1}\\ T(n-1) + O(n) & \mbox{if n > 1} \end{array}\right. \$$$$T(n - 1)$$ - For recursively sorting the previous (n - 1) elements.$$O(n)$$ - Running time for choosing the appropriate position of the element in the sorted array. $$T(n) = T(n-1) + n \\\hspace{0.75cm} = n + (n-1) + T(n-2) \\\hspace{0.75cm} = n + (n-1)+ (n-2)+ T(n-3) \\ \hspace{0.75cm} = n + (n-1)+ (n-2)+ ....+2 + T(1) \\ \hspace{0.75cm} = n(n-1)/2 + \theta (1) \\ \hspace{0.75cm} = \theta (n^{2}).$$So, $$T(n) = O(n^{2}).$$public static int[] RecursiveInsertionSort(int[] array, int n) { int i; if (n > 1) RecursiveInsertionSort(array, n - 1); else { int k = array[n]; i = n - 1; while (i >= 0 & & array[i] > k) { array[i + 1] = array[i]; i = i - 1; } array[i + 1] = k; } return array; }