Algorithm Analysis of Insertion Sort

Question

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?

Answer 1

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.