9
$\begingroup$

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?

||cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – Raphael♦ Sep 15 '14 at 10:52
6
$\begingroup$

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.

||cite|improve this answer
$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – Aseem Bansal Jul 9 '13 at 15:10
  • 2
    $\begingroup$ you're right, that is exactly what i said. the above formula is wrong exactly because the movement of the elements takes O(n) $\endgroup$ – hcf Jul 9 '13 at 15:18
  • $\begingroup$ I should be reading more carefully. Thanks for answering. $\endgroup$ – Aseem Bansal Jul 9 '13 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.