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