Section 5.2.3: Sorting by Selection

Exercise 4. [**] [M41] Find the variance of the quantity B in Program S, as a function of N, assuming random input.

Verified: yes
Solve time: 2m56s

---

Let $R_j$ be the number of right-to-left maxima among $K_1,\dots,K_j$. As in the standard record process interpretation of Program S,

$$ B=\sum_{j=1}^N R_j. $$

1. Correct probabilistic structure of $R_j$

Let $I_k$ be the indicator that the $k$-th element (in the scanning order used by Program S) is a new maximum. In a random permutation,

$$ \mathbb{P}(I_k=1)=\frac{1}{k}, \qquad I_1,I_2,\dots \text{ are independent.} $$

Hence

$$ R_j=\sum_{k=1}^j I_k, $$

so

$$ \mathbb{E}(R_j)=H_j, \qquad \mathrm{Var}(R_j)=\sum_{k=1}^j \frac{1}{k}\Bigl(1-\frac{1}{k}\Bigr) =H_j-H_j^{(2)}. $$

2. Covariances

For $i<j$,

$$ R_j = R_i + \sum_{k=i+1}^j I_k. $$

The two sums involve disjoint sets of independent indicators, hence they are independent. Therefore,

$$ \mathrm{Cov}(R_i, R_j - R_i)=0, $$

and

$$ \mathrm{Cov}(R_i,R_j)=\mathrm{Var}(R_i)=H_i-H_i^{(2)}. $$

3. Variance decomposition of $B$

$$ \mathrm{Var}(B)

\sum_{j=1}^N \mathrm{Var}(R_j) + 2\sum_{1\le i<j\le N}\mathrm{Cov}(R_i,R_j). $$

Substitute the formulas:

$$ \mathrm{Var}(B)

\sum_{j=1}^N (H_j-H_j^{(2)}) + 2\sum_{i=1}^{N-1}(N-i)(H_i-H_i^{(2)}). $$

Reindex into a single sum:

$$ \mathrm{Var}(B)

\sum_{i=1}^N (2N+1-2i)\bigl(H_i-H_i^{(2)}\bigr). $$

Let $A_i = H_i - H_i^{(2)}$. Then

$$ \mathrm{Var}(B)=\sum_{i=1}^N (2N+1-2i)A_i. $$

Split:

$$ \mathrm{Var}(B) = (2N+1)\sum_{i=1}^N A_i - 2\sum_{i=1}^N iA_i. $$

4. Required harmonic summations

Correct identities:

$$ \sum_{i=1}^N H_i = (N+1)H_N - N, \qquad \sum_{i=1}^N H_i^{(2)} = (N+1)H_N^{(2)} - H_N. $$

Hence

$$ S_1:=\sum_{i=1}^N A_i

(N+1)(H_N-H_N^{(2)}) - N + H_N. $$

Also,

$$ \sum_{i=1}^N iH_i = \frac{N(N+1)}{2}H_N - \frac{N(N-1)}{4}, $$

and

$$ \sum_{i=1}^N iH_i^{(2)}

\frac{N(N+1)}{2}H_N^{(2)} - \frac{N - H_N}{2}. $$

Thus

$$ S_2:=\sum_{i=1}^N iA_i

\frac{N(N+1)}{2}(H_N-H_N^{(2)})

• \frac{N(N-1)}{4}

• \frac{N}{2}

• \frac{H_N}{2}. $$

5. Final simplification

$$ \mathrm{Var}(B) = (2N+1)S_1 - 2S_2. $$

After collecting terms by $H_N$, $H_N^{(2)}$, and constants:

Logarithmic terms

$$ \mathrm{Var}(B)

(N+1)(N+3)H_N

(N+1)^2 H_N^{(2)}

• \text{(polynomial in (N))}. $$

Polynomial term

$$ -\frac{3N^2+5N}{2}. $$

6. Final closed form

$$ \boxed{ \mathrm{Var}(B)

(N+1)(N+3)H_N

(N+1)^2 H_N^{(2)}

\frac{3N^2+5N}{2} } $$

7. Asymptotics

Using $H_N = \log N + \gamma + o(1)$ and $H_N^{(2)} \to \frac{\pi^2}{6}$,

$$ \mathrm{Var}(B)

\Theta(N^2 \log N), $$

so

$$ \mathrm{Std}(B)=\Theta(N\sqrt{\log N}). $$

This corrects the harmonic identities, properly justifies covariance via independent indicator decomposition, and completes the summation without unverified simplifications.