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?
Here is a recursive version of insertion sort:
Input: array $A_1,\ldots,A_n$
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.