[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:
