Insertion sort can be expressed as a recursive procedure as follows. In order to sort $A[1 . . n]$, we recursively sort $A[1 . . n−1]$ and then insert A[n] into the sorted array $A[1 . . n − 1]$. Write a recurrence for the running time of this recursive version of insertion sort.

There are two steps in this recursive sorting algorithm:

1. Sort the sub-array $A[1 .. n - 1]$
2. Insert $A[n]$ into the sorted sub-array from step 1 in proper position

For $n = 1$, step 1 doesn’t take any time as the sub-array is an empty array and step 2 takes constant time, i.e. the algorithm runs in $\Theta(1)$ time.

For $n > 1$, step 1 again calls for the recursion for $n - 1$ and step 2 runs in $\Theta(n)$ time.

So, we can write the recurrence as:

Pseudo-code #1: RECURSE-INSERTION-SORT(A, n)
Pseudo-code #2: INSERT(A, k)
Solution to the Recurrence: Let us assume that for $n = 1$, $T(n) = c_1$, where $c_1$ is some constant. And on average for $n > 1$, inserting an element in its proper position in a sorted array requires shifting half of the elements, i.e. $c_2n/2 + c_3$ time ($c_2n/2$ for shifting the elements and $c_3$ for inserting the element).
So for any general $n > 1$,