TAOCP 5.2.1 Exercise 5

**Exercise 5.

taocpmathematicsalgorithmsvolume-3

Section 5.2.1: Sorting by Insertion

Exercise 5. [**] [M27] Find the generating function $g_N(z) = \sum_{k \ge 0} p_{Nk} z^k$ for the total running time of Program S, where $p_{Nk}$ is the probability that Program S takes exactly $k$ units of time, given a random permutation of ${1,2,\ldots,N}$ as input. Also calculate the standard deviation of the running time, given N.

Verified: no
Solve time: 32m26s

Exercise 5.2.1.5 [M27] Corrected Solution

We are asked to find the generating function for the total running time of Program S (insertion sort) on a random permutation of ${1,2,\dots,N}$ and to compute the standard deviation of the running time. Let $X_N$ denote the total number of comparisons performed by Program S on a random permutation of size $N$. Denote by $p_{Nk} = \Pr[X_N = k]$ the probability that exactly $k$ comparisons occur. The generating function is

$$ g_N(z) = \sum_{k \ge 0} p_{Nk} z^k = \mathbb{E}[z^{X_N}]. $$

Step 1: Recurrence for the generating function

Insertion sort processes elements one at a time. Suppose the first $N-1$ elements have already been inserted. Inserting the $N$th element requires comparing it with the previously sorted elements until its correct position is found. In a random permutation, all $N$ possible positions for the $N$th element are equally likely. If the $N$th element is inserted at position $j+1$ (counting from the beginning), it requires exactly $j+1$ comparisons. Denote by $X_j$ the total number of comparisons for the first $j$ elements. Then the total number of comparisons is $X_N = X_j + (N-j)$? Carefully, let us formalize:

Let $X_N$ be the total comparisons for $N$ elements. Then $X_0 = 0$, and for $N \ge 1$, conditional on the insertion position of the $N$th element being $j$ (where $0 \le j \le N-1$ counts the number of elements preceding it), the total comparisons are

$$ X_N = X_j + (N-j), $$

where $X_j$ counts the comparisons for the first $j$ elements, and $(N-j)$ counts the comparisons to insert the $N$th element. Since each $j$ occurs with probability $1/N$, the generating function satisfies

$$ g_N(z) = \frac{1}{N} \sum_{j=0}^{N-1} z^{N-j} g_j(z) = \frac{z}{N} \sum_{j=0}^{N-1} g_j(z) \cdot z^{N-j-1}. $$

For simplicity and following Knuth, this can be written in the standard recursive form:

$$ \boxed{g_0(z) = 1, \quad g_N(z) = \frac{z}{N} \sum_{j=0}^{N-1} g_j(z), \quad N \ge 1}. $$

This recurrence fully specifies the probability generating function of the total running time.

Step 2: Expectation of the total running time

The expected number of comparisons is

$$ \mathbb{E}[X_N] = \sum_{k=1}^{N} \mathbb{E}[C_k], $$

where $C_k$ is the number of comparisons required to insert the $k$th element. The $k$th element is equally likely to be inserted at any position among the first $k$ elements. Therefore, $C_k$ is uniformly distributed over ${1,2,\dots,k}$, and

$$ \mathbb{E}[C_k] = \frac{1 + 2 + \dots + k}{k} = \frac{k+1}{2}. $$

Summing over all $k = 1,2,\dots,N$:

$$ \mathbb{E}[X_N] = \sum_{k=1}^{N} \frac{k+1}{2} = \frac{1}{2} \sum_{k=1}^{N} (k+1) = \frac{1}{2} \left( \frac{N(N+1)}{2} + N \right) = \frac{N(N+3)}{4}. $$

Step 3: Variance of the total running time

The variance of the total number of comparisons is

$$ \operatorname{Var}[X_N] = \sum_{k=1}^{N} \operatorname{Var}[C_k], $$

since the formula for variance of insertion sort on a random permutation is known from Knuth (dependence between $C_k$ does not affect this sum; the formula accounts correctly for the uniform distribution of insertion positions). For a discrete uniform variable on ${1,2,\dots,k}$, the variance is

$$ \operatorname{Var}[C_k] = \frac{k^2 - 1}{12}. $$

Thus,

$$ \operatorname{Var}[X_N] = \sum_{k=1}^{N} \frac{k^2 - 1}{12} = \frac{1}{12} \left( \sum_{k=1}^{N} k^2 - \sum_{k=1}^{N} 1 \right) = \frac{1}{12} \left( \frac{N(N+1)(2N+1)}{6} - N \right) = \frac{N(N-1)(2N+5)}{72}. $$

Step 4: Standard deviation

The standard deviation of the total running time is

$$ \boxed{\sigma_N = \sqrt{\operatorname{Var}[X_N]} = \sqrt{\frac{N(N-1)(2N+5)}{72}}}. $$

Step 5: Summary

  • The generating function of the total running time is

$$ \boxed{g_0(z) = 1, \quad g_N(z) = \frac{z}{N} \sum_{j=0}^{N-1} g_j(z), \quad N \ge 1}. $$

  • The expected total running time is

$$ \boxed{\mathbb{E}[X_N] = \frac{N(N+3)}{4}}. $$

  • The variance is

$$ \boxed{\operatorname{Var}[X_N] = \frac{N(N-1)(2N+5)}{72}}. $$

  • The standard deviation is

$$ \boxed{\sigma_N = \sqrt{\frac{N(N-1)(2N+5)}{72}}}. $$