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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.