-1
$\begingroup$

I have a variant of Insertion sort (recursive version) that we call split insertion sort because there are two kinds of input. The input array has both numbers and alphabets, hence we have to sort them as two different arrays one for numbers and other one for alphabets. What would be the recurrence equatiuon for this variant of insertion sort

$\endgroup$
2
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Sep 12 '18 at 5:45
  • $\begingroup$ Without you actually giving the algorithm, little can be done to help you. Also, what have you tried and where did you get stuck? $\endgroup$ – Raphael Sep 12 '18 at 5:45
1
$\begingroup$

Insertion sort works as follows: At iteration $i$, we have $A[1\ldots(i-1)] $ sorted. So, the idea is to grab $A[i]$ and find the right position in $A[1\ldots(i-1)]$. Worst case would be for $A[i]$ to sit in the first position of $A[1\ldots(i-1)] $. Translating this to recursions, you will have \begin{align} T(n) &= T(n-1) + n\\ &=T(n-2) + n-1 + n \\ &= \vdots \\ &=T(n-k) + \sum_{i=0}^k (n - i) \end{align} Algorithm terminates at $k = n$, i.e. we shall get $$T(n) = T(0) + \sum_{i=0}^n (n - i)$$ where $T(0) = O(1)$. So, upon a change of variable, we get $$T(n) = \sum_{i=0}^n i = \frac{n(n+1)}{2} = O(n^2)$$

$\endgroup$

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