• 1

Recursive version of Insertion Sort
  • basicsorting
  • sorting
  • recursion
  • insertionsort
  • timecomplexity
  • array
  •   
    subscribe
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (31357)

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 Answers

  • Posted: 7 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;
 }
You need to Sign In to post your solution.