Exercise 2.3.4

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.

The recurrence is

$$ T(n) = \begin{cases} \Theta(1) & \text{if } n = 1, \\ T(n-1) + C(n-1) & \text{otherwise}. \end{cases} $$

where $C(n)$ is the time to insert an element in a sorted array of $n$ elements.