# Finding recurrence equation for a variant of insertion sort [closed]

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

• 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! – Raphael Sep 12 '18 at 5:45
• Without you actually giving the algorithm, little can be done to help you. Also, what have you tried and where did you get stuck? – Raphael Sep 12 '18 at 5:45

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)$$