[Introduction to Algorithms, CLRS] Exercises 2.3-4

This is a solution for Introduction to Algorithms. I write this for my study purpose.

Exercises 2.3-4

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

Answer:

There are two steps in this recursive sorting algorithm:

1. Sort the sub-array A[1..n−1]

2. Insert A[n] into the sorted sub-array from step 1 in proper position

For n=1, 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 Θ(1) time.

For n>1, step 1 again calls for the recursion for n−1 and step 2 runs in Θ(n) time.

So, we can write the recurrence as:

source: https://atekihcan.github.io/CLRS/E02.03-04/