We can express insertion sort 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 for the running time of this recursive version of insertion sort