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