Recurrence for recursive insertion sort

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?

Asked By : Aseem Bansal

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13168