Computer Science, Algorithm Design and Analysis class

Insertion sort can be expressed as a recursive procedure. To sort A[1 . . . n], we recursively sort A[1 . . . n1] and then insert A[n] into the sorted array A[1 . . . n1]. Write a recurrence for the running time of this recursive version of insertion sort.