Search for question
Question

Question 510 points

Insertion sort can be expressed as a recursive procedure as follows. In order

to sort A[1...n], we recursively sort A[1...n-1] and then insert A[n] into the sorted

array A[1.. n-1]. Write a recurrence (T(n) as a function of input size n) for the

running time of this recursive version of insertion sort.

Fig: 1