I tried this problem from CLRS (Page 39, 2.3-4)
We can express insertion sort as a recursive procedure as follows. In order to sort
A[1... n]
, we recursively sortA[1... n-1]
and then insertA[n]
into the sorted arrayA[1... n-1]
. Write a recurrence for the running time of this recursive version of insertion sort.
The recurrence I formed was
$$ T(n) = \begin{cases}\Theta(1) & \textrm{if } n = 1,\\ T(n-1) + \Theta(n) & \textrm{if } n > 1. \end{cases} $$
My reasoning
- the base case of $n = 1$ the list is sorted so there is no work hence constant time.
- For all other cases the time depends on sorting the sequence
A[1...n-1]
and then insertion into that sequence. Hence it should be their sum, i.e., $T(n-1) + \Theta(n)$.
I wanted to know whether the recurrence relation is correct. If not what are the mistakes and how to correctly formulate a recurrence relation?