CLRS Exercises 2.3-4 Recursive insertion sort

Problem:

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.

Solution:

1. Initially the array size will be n
2. call insertionsort function until the size becomes 1
3. then start the normal insertion approach as shown in code

T(n) = T(n-1) + 1 +  O(n) = O(n^2)

Complexity: O(n^2) TC
Code: