1
$\begingroup$

Why is the recurrence formula for insertion sort is T(n-1) + n?

I understand the T(n-1) part but the why does the cost for merging results is n or linear. Do we have to merge in insertion sort?

$\endgroup$
1
$\begingroup$

Here is a recursive version of insertion sort:

Input: array $A_1,\ldots,A_n$

  1. If $n = 1$, output $A_1$. Otherwise, continue.
  2. Recursively sort $A_1,\ldots,A_{n-1}$ into $B_1,\ldots,B_{n-1}$.
  3. Insert $A_n$ into $B$.
  4. Output $B$.

If we denote by $T(n)$ the running time for arrays of length $n$, then step 2 takes time $T(n-1)$, whereas step 3 takes time $O(n)$. Combined, we get the recurrence $T(n) = T(n-1) + O(n)$, with base case $T(1) = O(1)$, corresponding to step 1.

$\endgroup$

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.