Insertion sort can be expressed as a recursive procedure as follows. In order to sort , we recursively sort and then insert A[n] into the sorted array . Write a recurrence for the running time of this recursive version of insertion sort.

There are two steps in this recursive sorting algorithm:

  1. Sort the sub-array
  2. Insert into the sorted sub-array from step 1 in proper position

For , step 1 doesn’t take any time as the sub-array is an empty array and step 2 takes constant time, i.e. the algorithm runs in time.

For , step 1 again calls for the recursion for and step 2 runs in time.

So, we can write the recurrence as:



Additional Analysis

Pseudo-code #1: RECURSE-INSERTION-SORT(A, n)

1
2
3
if n > 1
    RECURSE-INSERTION-SORT(A, n - 1)
    INSERT(A, n)

Pseudo-code #2: INSERT(A, k)

1
2
3
4
5
6
key = A[k]
index = k - 1
while index > 0 and A[index] > key
    A[index + 1] = A[index]
    index = index - 1
A[index + 1] = key

Solution to the Recurrence: Let us assume that for , , where is some constant. And on average for , inserting an element in its proper position in a sorted array requires shifting half of the elements, i.e. time ( for shifting the elements and for inserting the element).

So, we can rewrite the recurrence as:

So for any general ,

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.