Cormen Edition 3 Exercise 2.3 Question 4 (Page No. 38)

Question

We can express the insertion sort as a recursive procedure as follows.In order to sort $A[1\dots n]$, we recursively sort $A[1 \dots n-1]$ and then insert $A[n]$ into the sorted array $A[1 \dots n-1]$. Write a recurrence for the running time of this recursive version of insertion sort.

Answer 1

$T(n) = T(n-1) + \Theta(n)\ \ \ if\ n>1$

                $\Theta(1)\ \ \ \ \ \ \ \  \ \  \ \ \ \  \ \ \ \ \ \ \ \ \  if\ n=1$

Here $\Theta(n)$ is the time required for swapping the elements to create space for the element to be inserted.