Recurrence for recursive insertion sort

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 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 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?

According to the description you provided the recurrence is correct.

you might think it should be

T(n)=\begin{Bmatrix}
1 & ,\ n=1\\
T(n-1)\ +\ \Theta(log\ n) & ,\ otherwise
\end{Bmatrix}

because you can find the insertion place by using Binary-Search, however in order to actually insert the element you'll have to move away all the elements in the worst case.

StackExchange Computer Science Q#13168, answer score: 6