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

• You may be interested in our reference questions. In particular, the notion of "runtime" is fuzzy, the recurrence with $\Theta$-terms is not the nicest way of putting things and several kinds of solving recurrences have been discussed. Note that "yes-no"-questions are generally undesired here. (I note that the question is old; leaving the comment for reference.) – Raphael Sep 15 '14 at 10:52

• Searching linearly takes O(n) and by doing binary search it is O(log n). But isn't the worst-case the movement of all the elements which should take O(n) hence making the overall complexity O(n)? So why is the term in n != 1 is O(log n) instead of being O(n)? – Aseem Bansal Jul 9 '13 at 15:10