CLRS Solutions | Exercise 2.3-4

We can express insertion sort 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:

Sort the sub-array $A[1..n-1]$
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:

\[T(n) = \begin {cases} \Theta(1) & \text { if } n = 1, \\ T(n - 1) + \Theta(n) & \text { if } n > 1 \end {cases}\]

Additional Analysis

Although it has not been asked in the problem statement, let us try to solve the recurrence for practice the same way it was done for $\textsc {Insertion-Sort}$ in the book or for $\textsc {Selection-Sort}$ in Exercise 2.2-2.

Let us first write the pseudocode for auxiliary procedure required to insert $A[n]$ into the sorted array as follows …

$$\textsc {Insert }(A, k)$$$$\begin{aligned}1& \quad key=A[k] \\2& \quad index=k-1 \\3& \quad \textbf {while }index>0\text { and }A[index]>key \\4& \quad \qquad A[index+1]=A[index] \\5& \quad \qquad index=index-1 \\6& \quad A[index+1]=key \\\end{aligned}$$

And recursive insertion sort as follows …

$$\textsc {Recurse-Insertion-Sort }(A, n)$$$$\begin{aligned}1& \quad \textbf {if }n>1 \\2& \quad \qquad \textsc {Recurse-Insertion-Sort}(A,\,n-1) \\3& \quad \qquad \textsc {Insert}(A,\,n) \\\end{aligned}$$

Intuitive Solution

As it is probably evident from the pseudocode, to insert the an element in a sorted sorted array in its’ rightful position, we’ll need to shift some of the elements to the right to make space for the new element.

In the worst case, when the new element is smaller than all elements in the array, all the $n$ elements has to be shifted. Which means it’ll be $\Theta(n)$ operation.

In the average case, we can assume the new element will smaller than half of the elements and larger than the other half. Which means we will need to shift $n/2$ elements, which is again a $\Theta(n)$ operation.

And this shifting has to be done for all of the $n$ elements one by one while recursing. Which makes the complete algorithm run at $n \times \Theta(n) = \Theta(n^2)$.

An exhaustive calculation is provided below for the sake of completeness.

Exhaustive Proof

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 (as explained above), i.e. $c_2n/2 + c_3$ time ($c_2n/2$ for shifting the elements and $c_3$ for inserting the element).

So, we can rewrite the recurrence as:

\[T(n) = \begin {cases} c_1 & \text { if } n = 1, \\ T(n - 1) + c_2 \frac {(n - 1)} 2 + c_3 & \text { if } n > 1 \end {cases}\]

So for any general $n > 1$,

\[\begin {aligned} T(n) & = T(n - 1) + c_2 \frac {(n - 1)} 2 + c_3 \\ & = \left( T(n - 2) + c_2 \frac {(n - 2)} 2 + c_3 \right) + c_2 \frac {(n - 1)} 2 + c_3 \\ & = T(1) + \cdots + \left( c_2 \frac {(n - 2)} 2 + c_3 \right) + \left( c_2 \frac {(n - 1)} 2 + c_3 \right) \\ & = c_1 + \frac {c_2} 2 \left(1 + 2 + \cdot \cdot \cdot + (n - 1)\right) + c_3(n - 1) \\ & = c_1 + \frac {c_2} 2 \cdot \frac {n(n - 1)} 2 + c_3(n - 1) \\ & = \Theta(n^2) \end {aligned}\]