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

Our division of the problem yields 1 subproblem of size \(\frac{n}{n-1}\). Dividing the problem takes constant \(\Theta(1)\) time, whereas solving it in the worst case takes \(\Theta(n-1)\) time. Using our recurrence calculation (pg.35):

\[T(n) = \begin{cases} \Theta(1) & \text{if $n=1$} \\ T(n-1) + \Theta(n) & \text{if $n>1$} \\ \end{cases}\]