TAOCP 5.2.2 Exercise 32

Section 5.2.2: Sorting by Exchanging

Exercise 32. [M10] Find a simple closed form expression for $C_{mn}$, the average number of key comparisons required to select the $m$th smallest of $n$ elements by the "quickfind" method of exercise 31. (For simplicity, let $M = 1$; that is, don't assume the use of a special technique for short subfiles.) What is the asymptotic behavior of $C_{(2m-1)m}$, the average number of comparisons needed to find the median of $2m - 1$ elements by Hoare's method?

Verified: no
Solve time: 1h11m

We need to solve Exercise 32 from TAOCP Volume 3, Section 5.2.2. The exercise: "Find a simple closed form expression for C_{mn}, the average number of key comparisons required to select the mth smallest of n elements by the 'quickfind' method of exercise 31. (For simplicity, let M = 1; that is, don't assume the use of a special technique for short subfiles.) What is the asymptotic behavior of C_{(2m-1)m}, the average number of comparisons needed to find the median of 2m - 1 elements by Hoare's method?"

We need to derive the average number of comparisons for quickselect (Hoare's FIND algorithm) to find the m-th smallest of n elements, with M=1 (no cutoff for small subfiles). Then find asymptotic behavior for median of 2m-1 elements, i.e., n = 2m-1, m = (n+1)/2.

First, recall the quickfind algorithm (exercise 31): it's the selection algorithm based on quicksort partitioning. We partition the array around a pivot, then recurse on the side containing the desired order statistic. The pivot is chosen as the first element? In Hoare's original method, the pivot is the first element. The analysis of average comparisons for quickselect is classic.

We need C_{mn}, average number of comparisons to find m-th smallest of n distinct elements, assuming all permutations equally likely, and pivot chosen as first element (or random pivot? Usually in quicksort analysis, pivot is first element, and since input is random permutation, it's equivalent to random pivot). The algorithm: partition the array by comparing each other element with pivot. Number of comparisons in partitioning n elements is n-1 (compare pivot with each of the other n-1 elements). After partitioning, pivot ends up at some position k (1 <= k <= n). If k = m, we are done. If k > m, we recurse on left subarray of size k-1 to find m-th smallest. If k < m, we recurse on right subarray of size n-k to find (m-k)-th smallest.

The pivot position k is uniformly distributed over {1,...,n} because input is random permutation. So we have recurrence:

C_{mn} = n-1 + (1/n) * [ sum_{k=1}^{m-1} C_{m-k, n-k} + sum_{k=m+1}^{n} C_{m, k-1} ] for 1 <= m <= n. Boundary: C_{11} = 0? Actually if n=1, no comparisons needed? Wait: if n=1, we have the element, no comparisons. But our recurrence uses n-1 comparisons for partitioning. For n=1, n-1=0, and there are no recursive calls because m=1=k. So C_{11}=0.

We need to solve this recurrence for C_{mn}. Known result: average number of comparisons for quickselect is 2n + o(n) for fixed m? Actually for finding the minimum (m=1) or maximum (m=n), it's 2n - O(log n)? Let's derive.

Standard result from Knuth or Hoare: The average number of comparisons to find the m-th smallest of n is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n+1-m} - 2(m+1)H_m + 2n + 2? Wait need exact.

I recall the formula: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? Or something like that. Let's derive carefully.

We have recurrence: C_{mn} = n-1 + (1/n) [ sum_{i=1}^{m-1} C_{m-i, n-i} + sum_{i=m+1}^{n} C_{m, i-1} ], for 1 <= m <= n. Let's change indices: for k from 1 to m-1, left recursion size = k-1? Wait: if pivot position is k (1-indexed), then left subarray has size k-1, right has size n-k. If k < m, we recurse on right subarray of size n-k, looking for (m-k)-th smallest. If k > m, we recurse on left subarray of size k-1, looking for m-th smallest. So: For k=1..m-1: right subarray size = n-k, rank = m-k. For k=m+1..n: left subarray size = k-1, rank = m. So recurrence: C_{mn} = n-1 + (1/n) [ sum_{k=1}^{m-1} C_{m-k, n-k} + sum_{k=m+1}^{n} C_{m, k-1} ].

This is standard. We can solve using generating functions or by guessing pattern.

Let's compute small values to guess formula.

Define C_{mn} for 1<=m<=n. C_{11}=0. For n=2: C_{12} = 1 + (1/2)[ sum_{k=1}^{0}... + sum_{k=2}^{2} C_{1,1} ] = 1 + (1/2)*0 = 1. C_{22} = 1 + (1/2)[ sum_{k=1}^{1} C_{1,1} + sum_{k=3}^{2}... ] = 1 + (1/2)*0 = 1. So C_{12}=C_{22}=1.

For n=3: C_{13} = 2 + (1/3)[ sum_{k=2}^{3} C_{1,k-1} ] = 2 + (1/3)(C_{11}+C_{12}) = 2 + (1/3)(0+1)=2 + 1/3 = 7/3 ≈ 2.333. C_{23} = 2 + (1/3)[ sum_{k=1}^{1} C_{1,2} + sum_{k=3}^{3} C_{2,2} ] = 2 + (1/3)(C_{12}+C_{22}) = 2 + (1/3)(1+1)=2 + 2/3 = 8/3 ≈ 2.667. C_{33} = 2 + (1/3)[ sum_{k=1}^{2} C_{2,2}? Wait: m=3, sum_{k=1}^{2} C_{3-k, 3-k} = C_{2,2}+C_{1,1} = 1+0=1] = 2 + 1/3 = 7/3. Symmetry: C_{mn} = C_{n+1-m, n}. So C_{13}=C_{33}=7/3.

For n=4: C_{14} = 3 + (1/4) sum_{k=2}^{4} C_{1,k-1} = 3 + (1/4)(C_{11}+C_{12}+C_{13}) = 3 + (1/4)(0+1+7/3)=3 + (1/4)(10/3)=3+10/12=3+5/6=23/6≈3.833. C_{24} = 3 + (1/4)[ sum_{k=1}^{1} C_{1,3} + sum_{k=3}^{4} C_{2,k-1} ] = 3 + (1/4)(C_{13}+C_{22}+C_{23}) = 3 + (1/4)(7/3+1+8/3)=3 + (1/4)(7/3+3/3+8/3)=3+(1/4)(18/3)=3+1.5=4.5=9/2. C_{34} = 3 + (1/4)[ sum_{k=1}^{2} C_{2,3}? Wait m=3: sum_{k=1}^{2} C_{3-k,4-k} = C_{2,3}+C_{1,2} = C_{23}+C_{12} = 8/3+1=11/3. sum_{k=4}^{4} C_{3,3} = C_{33}=7/3. Total = 18/3=6. So C_{34}=3+6/4=3+1.5=4.5. Symmetry holds. C_{44} = 3 + (1/4) sum_{k=1}^{3} C_{4-k,4-k} = 3 + (1/4)(C_{33}+C_{22}+C_{11}) = 3 + (1/4)(7/3+1+0)=3+10/12=23/6.

Now look for formula. Known result from Knuth's "The Art of Computer Programming", Volume 3, Section 5.2.3 (maybe) or in exercises. Actually the quickselect analysis is in Section 5.2.3? Wait, exercise 31 is in Section 5.2.2, but quicksort is in 5.2.2? Actually quicksort is discussed in 5.2.2? The context says "partition exchange (Hoare's 'quicksort')" in 5.2.2. Exercise 31 is about quickselect. So we need to find C_{mn}.

I recall the exact average number of comparisons for quickselect (Hoare's FIND) is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? Let's test with n=3,m=2. H_3 = 1+1/2+1/3 = 11/6. H_{2} = 1+1/2=3/2. H_{2}=3/2? Wait n-m+1 = 3-2+1=2. m=2. Compute: 2(4)H_3 - 2(3+2-2?) Wait n+2-m = 3+2-2=3? Actually n+2-m = 5-2=3. H_{n-m+1}=H_2=3/2. 2(m+1)H_m = 23H_2 = 6*(3/2)=9. 2n+2=8. 24(11/6) = 811/6 = 88/6 = 44/3 ≈ 14.667. 23*(3/2) = 9. So 44/3 - 9 - 9 + 8 = 44/3 - 10 = 44/3 - 30/3 = 14/3 ≈ 4.667. But C_{23}=8/3≈2.667. So that's not right.

Maybe formula is: C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n-m} - 2(m+1)H_m + 2n? Let's test. n=3,m=2: H_3=11/6, H_1=1, H_2=3/2. 2411/6 = 88/6 = 44/3. 2*(3+1-2?) n+1-m = 2? H_{n-m}=H_1=1. So 221=4. 2*(m+1)H_m = 231.5=9. 2n=6. 44/3 -4 -9 +6 = 44/3 -7 = 44/3 -21/3 = 23/3 ≈ 7.667. Not 8/3.

Maybe C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n+1-m} - 2(m+1)H_m + 2n? That gave 44/3 - 22H_2? n+1-m = 2, H_2=3/2, so 221.5=6. 231.5=9. 44/3 -6 -9 +6 = 44/3 -9 = 17/3 ≈5.667.

Another known formula: The average number of comparisons for quickselect is: C_{mn} = 2(n+1)H_n - 2(n+3-2m)H_{n-m+1}? No.

Let's derive from scratch.

We have recurrence: C_{mn} = n-1 + (1/n) [ sum_{k=1}^{m-1} C_{m-k, n-k} + sum_{k=m+1}^{n} C_{m, k-1} ].

Multiply by n: n C_{mn} = n(n-1) + sum_{k=1}^{m-1} C_{m-k, n-k} + sum_{k=m+1}^{n} C_{m, k-1}.

We can try to find a pattern by computing differences or using known results. Let's define D_{mn} = C_{mn} + something.

Alternatively, known result from Hoare's paper or Knuth's book: The average number of comparisons for FIND is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? Wait, I've seen: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? Let's test n=2,m=1: H_2=1.5, H_2=1.5? n-m+1=2. m=1. 231.5 = 9. 2*(2+2-1)=23=6 * H_2=61.5=9. 2*(1+1)H_1=4*1=4. 2n+2=6. 9 -9 -4 +6 = 2. But C_{12}=1. So not.

Maybe it's C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n-m+1} - 2(m+1)H_m + 2n? n=2,m=1: 231.5=9. 2*(2+1-1)=22=4 * H_2=41.5=6. 221=4. 2n=4. 9-6-4+4=3. Not 1.

Maybe C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n+1-m} - 2(m+1)H_m + 2n? n=2,m=1: H_3? n+1=3? H_3=11/6. n+1-m=2? H_2=1.5. 2311/6=11. 221.5=6. 221=4. 2n=4. 11-6-4+4=5. No.

Let's check literature: The average number of comparisons in quickselect (Hoare's FIND) is known to be: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? That gave 2 for n=2,m=1 but correct is 1. Maybe the formula is for something else.

Wait, maybe the partitioning uses n comparisons? In some versions, pivot is compared with all other elements, so n-1 comparisons. But some analyses use n+1 comparisons? Or maybe the recurrence includes the comparison to check if k=m? No.

Let's re-derive carefully.

We have n elements. Choose pivot (first element). Compare pivot with each of the other n-1 elements. That's n-1 comparisons. After partitioning, pivot is in position k (1 <= k <= n). If k=m, done. If k < m, recurse on right subarray of size n-k, looking for (m-k)-th smallest. If k > m, recurse on left subarray of size k-1, looking for m-th smallest.

Thus recurrence: C_{mn} = n-1 + (1/n) * [ sum_{k=1}^{m-1} C_{m-k, n-k} + sum_{k=m+1}^{n} C_{m, k-1} ].

Let's compute C_{1n} (minimum). For m=1: C_{1n} = n-1 + (1/n) * sum_{k=2}^{n} C_{1, k-1} = n-1 + (1/n) * sum_{j=1}^{n-1} C_{1j}. Multiply by n: n C_{1n} = n(n-1) + sum_{j=1}^{n-1} C_{1j}. Similarly, for m=n: C_{nn} = n-1 + (1/n) sum_{k=1}^{n-1} C_{n-k, n-k} = n-1 + (1/n) sum_{j=1}^{n-1} C_{jj}. By symmetry C_{1n}=C_{nn}.

We can solve for C_{1n}. Let S_n = sum_{j=1}^{n} C_{1j}. Then n C_{1n} = n(n-1) + S_{n-1}. Also S_n = S_{n-1} + C_{1n}. So S_n = S_{n-1} + (n-1) + S_{n-1}/n = S_{n-1}(1 + 1/n) + n-1. This recurrence can be solved.

S_1 = C_{11} = 0. S_2 = S_1*(1+1/2) + 1 = 0 + 1 = 1. C_{12}=S_2-S_1=1. S_3 = S_2*(4/3) + 2 = 1*(4/3)+2 = 10/3. C_{13}=10/3 - 1 = 7/3. Matches. S_4 = S_3*(5/4) + 3 = (10/3)*(5/4)+3 = 50/12+3 = 25/6+18/6=43/6. C_{14}=43/6 - 10/3 = 43/6 - 20/6 = 23/6. Matches.

So we can find closed form for S_n. S_n = sum_{j=1}^n C_{1j}. Recurrence: S_n = ( (n+1)/n ) S_{n-1} + n-1. Multiply by n: n S_n = (n+1) S_{n-1} + n(n-1). Let T_n = n S_n. Then T_n = (n+1) S_{n-1} + n(n-1) = (n+1)/ (n-1) * T_{n-1}? Not directly. Actually S_{n-1} = T_{n-1}/(n-1). So T_n = (n+1)/(n-1) T_{n-1} + n(n-1). Better: Divide by (n+1)n? Standard method: divide by n(n+1)? We have S_n/(n+1) - S_{n-1}/n = (n-1)/(n+1)? Let's check. S_n = (n+1)/n S_{n-1} + n-1. Divide both sides by n+1: S_n/(n+1) = S_{n-1}/n + (n-1)/(n+1). So S_n/(n+1) = sum_{j=2}^n (j-1)/(j+1) + S_1/1? S_1=0. S_n/(n+1) = sum_{j=2}^n (j-1)/(j+1) = sum_{j=2}^n (1 - 2/(j+1)) = (n-1) - 2 sum_{j=2}^n 1/(j+1) = (n-1) - 2 (H_{n+1} - 1 - 1/2) = (n-1) - 2 H_{n+1} + 2 + 1 = n + 2 - 2 H_{n+1}. Thus S_n = (n+1)(n+2 - 2 H_{n+1}) = (n+1)(n+2) - 2(n+1)H_{n+1}. Then C_{1n} = S_n - S_{n-1} for n>=2. S_{n-1} = n(n+1 - 2 H_n). C_{1n} = (n+1)(n+2) - 2(n+1)H_{n+1} - n(n+1) + 2n H_n = (n+1)[(n+2)-n] - 2(n+1)H_{n+1} + 2n H_n = 2(n+1) - 2(n+1)H_{n+1} + 2n H_n. Since H_{n+1} = H_n + 1/(n+1), we have -2(n+1)(H_n + 1/(n+1)) + 2n H_n = -2(n+1)H_n - 2 + 2n H_n = -2H_n - 2. So C_{1n} = 2(n+1) - 2H_n - 2 = 2n - 2H_n? Wait: 2(n+1) - 2 = 2n. Then -2H_n? Let's recalc: C_{1n} = 2(n+1) - 2(n+1)H_{n+1} + 2n H_n. = 2(n+1) - 2(n+1)(H_n + 1/(n+1)) + 2n H_n = 2(n+1) - 2(n+1)H_n - 2 + 2n H_n = 2n - 2H_n. But for n=2: 22 - 21.5 = 4 - 3 = 1. Correct. n=3: 6 - 2*(11/6)=6 - 11/3=7/3. Correct. n=4: 8 - 2*(25/12)=8 - 25/6=23/6. Correct. So C_{1n} = 2n - 2H_n.

Now for general m. The recurrence is symmetric: C_{mn} = C_{n+1-m, n}. So we can assume m <= (n+1)/2.

We can try to find a pattern from small values. n=1: C_{11}=0. n=2: C_{12}=1, C_{22}=1. n=3: C_{13}=7/3, C_{23}=8/3, C_{33}=7/3. n=4: C_{14}=23/6, C_{24}=9/2=27/6, C_{34}=9/2, C_{44}=23/6. n=5: Let's compute to see pattern. C_{15} = 4 + (1/5) sum_{j=1}^{4} C_{1j} = 4 + S_4/5 = 4 + (43/6)/5 = 4 + 43/30 = 163/30 ≈ 5.4333. C_{25} = 4 + (1/5)[ C_{14} + sum_{k=3}^{5} C_{2,k-1} ] = 4 + (1/5)[ C_{14} + C_{22} + C_{23} + C_{24} ]. C_{14}=23/6≈3.833, C_{22}=1, C_{23}=8/3≈2.667, C_{24}=9/2=4.5. Sum = 23/6 + 1 + 8/3 + 9/2 = 23/6 + 6/6 + 16/6 + 27/6 = 72/6=12. So C_{25}=4+12/5=4+2.4=6.4=32/5=192/30? 6.4 = 192/30? 32/5=192/30? 32/5 = 192/30? 32/5=6.4, 192/30=6.4. C_{15}=163/30≈5.433. C_{35} = 4 + (1/5)[ sum_{k=1}^{2} C_{3-k,5-k} + sum_{k=4}^{5} C_{3,k-1} ]. k=1: C_{2,4}=C_{24}=9/2=4.5. k=2: C_{1,3}=7/3≈2.333. Sum left = 9/2+7/3=27/6+14/6=41/6≈6.833. k=4: C_{3,3}=7/3≈2.333. k=5: C_{3,4}=9/2=4.5. Sum right = 41/6? Wait C_{33}+C_{34}=7/3+9/2=14/6+27/6=41/6. Total = 82/6=41/3≈13.667. C_{35}=4 + (41/3)/5 = 4 + 41/15 = 60/15+41/15=101/15≈6.733. C_{45} = symmetric to C_{25} = 32/5 = 6.4. C_{55} = symmetric to C_{15} = 163/30 ≈5.433.

Now let's see if we can express in terms of harmonic numbers. C_{1n} = 2n - 2H_n. C_{2n}? For n=2: 1 = 4 - 2H_2? 4-3=1. 2n - 2H_n? n=2: 4-3=1. n=3: 6-2H_3=6-11/3=7/3≈2.333 but C_{23}=8/3≈2.667. So not that. Maybe C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? Let's test with n=3,m=2: 2411/6=44/3. 2*(3+2-2)=23=6 * H_2=61.5=9. 2*(2+1)H_2=6*1.5=9. 2n+2=8. 44/3 -9 -9 +8 = 44/3 -10 = 14/3 ≈4.667. No.

Maybe the formula is for number of comparisons including the final comparison? No.

Let's search memory: The average number of comparisons in quickselect (Hoare's FIND) is given by: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? That didn't match. Wait, maybe the recurrence is different: some analyses count the comparison of the pivot with itself? Or maybe the formula is for the number of comparisons in a variant where the pivot is compared with all n elements? Let's check Knuth's book. In TAOCP Vol 3, Section 5.2.3 (or maybe 5.2.2), the analysis of FIND is in the exercises? Actually exercise 31 is in 5.2.2, and exercise 32 asks for C_{mn}. The answer is likely in the back of the book. I recall a known formula: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? That gave 2 for n=2,m=1 but correct is 1. Could it be that the average number of comparisons is defined differently? For n=2, finding the minimum: compare the two elements once. So 1 comparison. The formula giving 2 would be off by 1.

Maybe the formula is C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n-m+1} - 2(m+1)H_m + 2n? For n=2,m=1: 231.5=9; 221.5=6; 221=4; 2n=4; 9-6-4+4=3. No.

Maybe it's C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n? n=2,m=1: 9 - 231.5? n+2-m=3, H_2=1.5 -> 9; 221=4; 2n=4; 9-9-4+4=0. No.

Let's derive the general solution. We have recurrence: n C_{mn} = n(n-1) + sum_{k=1}^{m-1} C_{m-k, n-k} + sum_{k=m+1}^{n} C_{m, k-1}. We can try to find a telescoping form. Define D_{mn} = C_{mn} + a(m,n) maybe.

Another approach: The average number of comparisons for quickselect is known to be: C_{mn} = 2(n+1)H_n - 2(n+3-2m)H_{n-m+1} - 2(m+1)H_m + something? No.

Let's look up known result: In "The Art of Computer Programming", Volume 3, Section 5.2.3, "Minimum-Comparison Selection", but that's different. The quickselect analysis is in the exercises. I think the answer to exercise 32 is given in the answers section. I recall the formula: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But that gave 2 for n=2,m=1. Maybe the recurrence in the book uses a different base? If M=1 means no cutoff for small subfiles, but maybe they count comparisons differently? Let's read exercise 31: "Suppose that, instead of sorting an entire file, you only want to determine the mth smallest of n elements. Show that quicksort can be adapted to this purpose, avoiding many of the computations required to do a complete sort." This is Hoare's FIND algorithm. In FIND, the partitioning step uses n-1 comparisons. So our recurrence is correct.

Maybe the formula in the book is C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? Let's test n=3,m=2 again: 2411/6=44/3=14.667; -23H_2=-9; -23H_2=-9; +2n+2=8; sum=14.667-10=4.667. But we got 8/3=2.667. So off by 2. For n=3,m=1: 2411/6=44/3; -24H_3? n+2-m=4, H_3=11/6 -> -2411/6 = -88/6 = -44/3; -22H_1=-4; +8; total = 44/3 -44/3 -4+8=4. But C_{13}=7/3≈2.333. Off by 5/3? Not constant.

Maybe the formula is C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n-m+1} - 2(m+1)H_m + 2n? n=3,m=1: 2411/6=44/3; -23H_3? n+1-m=3, H_3=11/6 -> -2311/6 = -11; -221=-4; +6; 44/3 -11 -4 +6 = 44/3 -9 = 17/3≈5.667. No.

Let's derive properly using generating functions or by solving the recurrence.

We have for 1 <= m <= n: C_{mn} = n-1 + (1/n) [ sum_{i=1}^{m-1} C_{m-i, n-i} + sum_{i=m+1}^{n} C_{m, i-1} ].

Let's change variable in first sum: let j = m-i, then i = m-j, j runs from m-1 down to 1? Actually i=1 -> j=m-1; i=m-1 -> j=1. So sum_{j=1}^{m-1} C_{j, n-m+j}. Second sum: let j = i-1, then j runs from m to n-1. Sum_{j=m}^{n-1} C_{m, j}.

So: n C_{mn} = n(n-1) + sum_{j=1}^{m-1} C_{j, n-m+j} + sum_{j=m}^{n-1} C_{m, j}. (1)

This is a standard recurrence. We can try to find a solution of the form: C_{mn} = A_n + B_m + something? But it's not separable simply.

We can use the approach of "difference" or "diagonal". Let's define for fixed d = n-m, the behavior. Or use the known result: C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n-m} - 2(m+1)H_m + 2n? That gave 23/3 for n=3,m=2? No.

Wait, I recall a paper by Hoare or Knuth: The average number of comparisons in FIND is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? Let's test with n=4,m=2. H_4 = 1+1/2+1/3+1/4 = 25/12 ≈ 2.08333. H_{3} = 1+1/2+1/3 = 11/6 ≈ 1.8333. H_2 = 1.5. Compute: 2525/12 = 250/12 = 125/6 ≈ 20.833. -2*(4+2-2)= -24= -8 * H_3 = -811/6 = -88/6 = -44/3 ≈ -14.667. -2*(2+1)H_2 = -61.5 = -9. +2n+2 = 10. Sum = 125/6 - 44/3 - 9 + 10 = 125/6 - 88/6 +1 = 37/6 +1 = 43/6 ≈ 7.167. But C_{24}=9/2=4.5. So not.

Maybe it's C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n+1-m} - 2(m+1)H_m + 2n? n=4,m=2: 2525/12=125/6; -23H_3= -611/6= -11; -23H_2= -61.5= -9; +8; sum=125/6 -20 +8 = 125/6 -12 = 125/6 -72/6=53/6≈8.833. No.

Let's try to find pattern from computed values: n=1: C11=0 n=2: C12=1, C22=1 n=3: C13=7/3≈2.333, C23=8/3≈2.667, C33=7/3 n=4: C14=23/6≈3.833, C24=9/2=4.5, C34=4.5, C44=23/6 n=5: C15=163/30≈5.433, C25=32/5=6.4, C35=101/15≈6.733, C45=6.4, C55=5.433

Let's compute C_{mn} - C_{m-1,n} maybe? Or look at differences along rows.

For n=3: C23-C13 = 1/3. n=4: C24-C14 = 9/2 - 23/6 = 27/6-23/6=4/6=2/3. C34-C24=0. n=5: C25-C15 = 32/5 - 163/30 = 192/30 - 163/30 = 29/30 ≈0.967. C35-C25 = 101/15 - 32/5 = 101/15 - 96/15 = 5/15=1/3≈0.333.

Not obvious.

Maybe we can derive using the "recurrence for expectations" method. Let E_{m,n} be the average comparisons. The recurrence is: E_{m,n} = n-1 + (1/n) [ sum_{k=1}^{m-1} E_{m-k, n-k} + sum_{k=m+1}^{n} E_{m, k-1} ]. We can try to guess that E_{m,n} = a n + b H_n + c m + d H_m + e H_{n-m+1} + ...

Another approach: The number of comparisons in quickselect is equal to the number of comparisons in quicksort but only on the path to the m-th element? Actually, quickselect only recurses on one side. There is a known identity: The expected number of comparisons to find the m-th smallest is equal to the expected number of comparisons in quicksort to sort the array, but only counting comparisons involving the m-th element? No.

Wait, I recall a result: The average number of comparisons in Hoare's FIND is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But that gave 2 for n=2,m=1. Could it be that the base case is C_{11}=1? If C_{11}=1, then for n=2,m=1: C_{12} = 1 + (1/2)*C_{11} = 1.5? Not 1.

Let's check the exact wording of exercise 32: "Find a simple closed form expression for C_{mn}, the average number of key comparisons required to select the mth smallest of n elements by the 'quickfind' method of exercise 31. (For simplicity, let M = 1; that is, don't assume the use of a special technique for short subfiles.)"

Maybe "quickfind" is slightly different? In some versions, the pivot is chosen randomly, and the partitioning compares the pivot with all other elements, but also maybe the pivot is compared with itself? No.

Let's search memory for the exact formula from Knuth's book. In the answer to exercise 32 (which is in the back of Vol 3), the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? I'm not sure.

Let's derive from scratch using a telescoping recurrence.

We have: n C_{mn} = n(n-1) + sum_{j=1}^{m-1} C_{j, n-m+j} + sum_{j=m}^{n-1} C_{m, j}. (A)

Consider the difference for fixed n: n C_{mn} - (n-1) C_{m-1,n}? Not straightforward.

Another technique: Define F_{m,n} = C_{mn} + 2? Or maybe we can find a recurrence for C_{mn} in terms of C_{m,n-1} and C_{m-1,n-1}.

Let's write recurrence for C_{m,n} and C_{m,n-1}: n C_{mn} = n(n-1) + sum_{j=1}^{m-1} C_{j, n-m+j} + sum_{j=m}^{n-1} C_{m, j}. (n-1) C_{m,n-1} = (n-1)(n-2) + sum_{j=1}^{m-1} C_{j, n-1-m+j} + sum_{j=m}^{n-2} C_{m, j}.

Subtract: n C_{mn} - (n-1) C_{m,n-1} = n(n-1) - (n-1)(n-2) + sum_{j=1}^{m-1} [C_{j, n-m+j} - C_{j, n-1-m+j}] + C_{m, n-1}. = 2(n-1) + sum_{j=1}^{m-1} [C_{j, n-m+j} - C_{j, n-m-1+j}] + C_{m, n-1}.

Not obviously telescoping.

Maybe we can use the fact that the expected number of comparisons in quickselect is equal to the expected number of comparisons in quicksort restricted to the set of elements that are compared with the m-th element? Actually, in quicksort, every pair of elements is compared at most once. The total comparisons in quicksort is sum over all pairs of indicator that they are compared. For quickselect, we only do partitioning until the m-th element is isolated. The comparisons performed are exactly those comparisons in quicksort that involve the m-th element? No, that's not true; we compare many other pairs as well.

Wait, there is a known relation: The average number of comparisons in quickselect is equal to the average number of comparisons in quicksort that involve the m-th element? Let's think: In quicksort, the m-th element will be compared with all elements that are ever in the same subarray as it before it becomes a pivot. In quickselect, we only partition subarrays that contain the m-th element, and we compare the pivot with all other elements in that subarray. So the set of comparisons in quickselect is exactly the set of comparisons in quicksort that involve the m-th element? Not exactly: In quickselect, when we partition a subarray containing the m-th element, we compare the pivot with all other elements in that subarray. The m-th element might not be the pivot; it might be compared with the pivot. In quicksort, the same comparisons happen when sorting that subarray. But in quicksort, we also partition subarrays that do not contain the m-th element. So the comparisons in quickselect are a subset of quicksort comparisons: those that occur in subarrays containing the m-th element. But the expected number of such comparisons can be computed.

In quicksort, the expected number of comparisons between a specific element (the m-th smallest) and all other elements is known: it's 2H_n - something? Actually, in quicksort, the probability that two specific elements are compared is 2/(j-i+1) if they are the i-th and j-th smallest? Wait: The probability that the i-th and j-th smallest are compared in quicksort is 2/(j-i+1). For the m-th element and another element of rank k, the probability they are compared is 2/(|m-k|+1). Then the expected number of comparisons involving the m-th element is sum_{k=1, k≠m}^n 2/(|m-k|+1) = 2(H_m + H_{n-m+1} - 1)? Let's compute: For k < m, distance = m-k, denominator = m-k+1. Sum_{d=1}^{m-1} 2/(d+1) = 2(H_m - 1). For k > m, distance = k-m, denominator = k-m+1. Sum_{d=1}^{n-m} 2/(d+1) = 2(H_{n-m+1} - 1). Total = 2(H_m + H_{n-m+1} - 2). But our C_{1n} = 2n - 2H_n, which for large n is ~2n, not ~2 log n. So that's not it. The quickselect does many more comparisons than just those involving the m-th element. In fact, it compares all elements in the subarrays that contain the m-th element. So it's the sum of sizes of those subarrays minus 1 each time.

There is a known formula for the expected number of comparisons in quickselect (Hoare's FIND) by Knuth or others. Let me recall: In "The Art of Computer Programming", Volume 3, Section 5.2.3, "Minimum-Comparison Selection", the analysis of FIND is given in the exercises? Actually, exercise 31 is in 5.2.2, and 32 is in 5.2.2. The answer might be in the back. I think the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But that didn't match. Let me re-check the recurrence. Maybe the number of comparisons in partitioning is n, not n-1? If we compare the pivot with all n elements including itself? That would be weird. Or maybe the algorithm does an extra comparison to check if the subfile size is 1? But M=1 means we don't use a special technique for short subfiles, so we just continue until size 1. For size 1, we don't do any comparisons. So n-1 is correct.

Wait, maybe the recurrence is: C_{mn} = n + (1/n) [ sum_{k=1}^{m-1} C_{m-k, n-k} + sum_{k=m+1}^{n} C_{m, k-1} ]? Let's test n=2,m=1: C_{12} = 2 + (1/2)*0 = 2. Not 1.

Maybe the recurrence includes the comparison to check if the pivot is the m-th? No.

Let's look at the values we computed: C_{1n} = 2n - 2H_n. For n=1, that would be 2 - 2 = 0. Good. C_{2n} for n=2:1, n=3:8/3≈2.667, n=4:4.5, n=5:6.4. Is there a pattern? C_{2n} = 2n - 2H_n + something? For n=3: 23 - 211/6 = 6 - 11/3 = 7/3 = 2.333, but C23=8/3. So C23 = C13 + 1/3. C24 = C14 + 2/3? C14=23/6=3.833, C24=4.5=27/6, diff=4/6=2/3. C25 = C15 + 29/30? C15=163/30≈5.433, C25=192/30=6.4, diff=29/30. Not a simple harmonic difference.

Maybe we can derive the general formula by solving the recurrence using generating functions or by noticing that C_{mn} satisfies a simpler recurrence in terms of differences.

Let's define D_{mn} = C_{mn} - C_{m-1,n} for m>=2. Then we might find a pattern.

From the recurrence (A): n C_{mn} = n(n-1) + sum_{j=1}^{m-1} C_{j, n-m+j} + sum_{j=m}^{n-1} C_{m, j}. For m-1: n C_{m-1,n} = n(n-1) + sum_{j=1}^{m-2} C_{j, n-m+1+j} + sum_{j=m-1}^{n-1} C_{m-1, j}.

Subtract: n (C_{mn} - C_{m-1,n}) = sum_{j=1}^{m-2} [C_{j, n-m+j} - C_{j, n-m+1+j}] + C_{m-1, n-m+1} - sum_{j=m-1}^{n-1} C_{m-1, j} + sum_{j=m}^{n-1} C_{m, j}. = - sum_{j=1}^{m-2} [C_{j, n-m+1+j} - C_{j, n-m+j}] + C_{m-1, n-m+1} - C_{m-1, m-1} - sum_{j=m}^{n-1} [C_{m-1, j} - C_{m, j}].

This seems messy.

Another approach: The problem is classic. The average number of comparisons in Hoare's FIND is given by: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? Let me check if I mis-evaluated for n=3,m=2. H_n = H_3 = 11/6. H_{n-m+1} = H_{2} = 3/2. H_m = H_2 = 3/2. 2(n+1)H_n = 2411/6 = 88/6 = 44/3. 2(n+2-m)H_{n-m+1} = 2*(3+2-2)3/2 = 233/2 = 9? Wait: 2 * (n+2-m) * H_{n-m+1} = 2 * 3 * 1.5 = 9. 2(m+1)H_m = 231.5 = 9. 2n+2 = 8. 44/3 - 9 - 9 + 8 = 44/3 - 10 = 14/3 ≈ 4.667. But we got 8/3. If the formula instead had +2n? 2n=6, then 44/3 -9 -9 +6 = 44/3 -12 = 8/3. Yes! 44/3 - 12 = 44/3 - 36/3 = 8/3. So if the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n. Check n=3,m=2: 2411/6 = 44/3. -231.5 = -9. -231.5 = -9. +6 = 6. 44/3 -12 = 8/3. Correct! Check n=3,m=1: 2411/6 = 44/3. -2(3+2-1)= -24= -8 * H_3? Wait n+2-m = 3+2-1=4. H_{n-m+1}=H_3=11/6. So -2411/6 = -88/6 = -44/3. -2(1+1)H_1 = -4*1 = -4. +2n=6. Sum = 44/3 -44/3 -4 +6 = 2. But C13=7/3≈2.333. So not correct for m=1.

Maybe the formula has H_{n-m} instead of H_{n-m+1}? Let's try: C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n-m+1} - 2(m+1)H_m + 2n. n=3,m=1: n+1-m=3, H_{n-m+1}=H_3=11/6. -2311/6 = -11. -221=-4. +6. 44/3 -11 -4 +6 = 44/3 -9 = 17/3≈5.667. No.

What about: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? We saw n=3,m=2 gives 14/3. So that's not.

Maybe the formula is different for m=1? But we need a single closed form.

Let's test another candidate: C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? n=3,m=2: 44/3 - 221.5? n+1-m=2, H_2=1.5 -> -6. -231.5=-9. +8. 44/3 -7 = 23/3≈7.667. No.

Maybe the formula is symmetric in m and n-m+1. Our C_{mn} = C_{n+1-m, n}. So the formula should be symmetric under m -> n+1-m. The expression 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n is symmetric? Let's check: replace m by n+1-m. Then n+2-m becomes n+2-(n+1-m)=m+1. And n-m+1 becomes n-(n+1-m)+1 = m. So the terms swap. So it is symmetric. But it gave C13=2, not 7/3. So maybe my computed C13 is wrong? Let's recompute C13 carefully.

n=3, m=1 (minimum). Recurrence: C13 = 2 + (1/3) * sum_{k=2}^{3} C_{1, k-1}. C11=0, C12=1. Sum = 1. So C13 = 2 + 1/3 = 7/3. That seems correct.

But wait, maybe the algorithm for "quickfind" is slightly different: In Hoare's FIND, the pivot is chosen as the first element, but the partitioning might be done differently? Or maybe the average number of comparisons includes the final comparison to check if the pivot is the desired one? No, that's not a key comparison.

Could it be that the recurrence is: C_{mn} = n + (1/n) [ sum_{k=1}^{m-1} C_{m-k, n-k} + sum_{k=m+1}^{n} C_{m, k-1} ]? Then C12 = 2? But we know from quickselect that finding min of 2 takes 1 comparison. So n-1 is correct.

Maybe the formula in the book uses a different definition: "average number of key comparisons" might count the comparison of the pivot with itself? Unlikely.

Let's check the values for C_{1n} from the formula C_{1n} = 2n - 2H_n. n=1: 0 n=2: 1 n=3: 7/3 ≈ 2.333 n=4: 23/6 ≈ 3.833 n=5: 163/30 ≈ 5.433

Now, is there a known formula that yields these? 2n - 2H_n = 2(n+1)H_n - 2(n+1)H_n? No.

Let's try to find a general expression that matches C_{1n} = 2n - 2H_n and C_{2n} values.

We have: C_{1n} = 2n - 2H_n. C_{2n} for n=2:1, n=3:8/3, n=4:9/2, n=5:32/5. Let's express C_{2n} in terms of harmonic numbers. n=2: 1 = 4 - 3 = 22 - 2H_2? 4-3=1. So C_{22} = 22 - 2H_2. n=3: 8/3 = 6 - 10/3? 6 - 3.333 = 2.667. 2*3 - 2H_3? 6 - 11/3 = 7/3. Not 8/3. Maybe C_{2n} = 2n - 2H_n + 2/(n)? n=3: 7/3 + 2/3 = 9/3=3, not 8/3. C_{2n} = 2n - 2H_n + 2/n? n=3: 7/3 + 2/3 = 3. No. C_{2n} = 2n - 2H_n + 2/(n+1)? n=3: 7/3 + 2/4 = 7/3+0.5=17/6≈2.833.

Let's compute differences: C_{2n} - C_{1n}: n=2: 0 n=3: 1/3 n=4: 2/3 n=5: 29/30? Wait 6.4 - 5.4333 = 0.9667 = 29/30. n=6? Let's compute C_{16} and C_{26} to see pattern. C_{16} = 5 + (1/6) sum_{j=1}^{5} C_{1j}. S_5 = S_4 + C_{15} = 43/6 + 163/30 = 215/30 + 163/30 = 378/30 = 63/5 = 12.6. C_{16} = 5 + 12.6/6 = 5 + 2.1 = 7.1 = 71/10? 5 + 63/30 = 5 + 21/10 = 50/10+21/10=71/10=7.1. C_{26} = 5 + (1/6)[ C_{15} + sum_{k=3}^{6} C_{2,k-1} ] = 5 + (1/6)[ C_{15} + C_{22} + C_{23} + C_{24} + C_{25} ]. C_{15}=163/30≈5.433, C22=1, C23=8/3≈2.667, C24=4.5, C25=6.4. Sum = 163/30 + 1 + 8/3 + 9/2 + 32/5. Common denominator 30: 163/30 + 30/30 + 80/30 + 135/30 + 192/30 = (163+30+80+135+192)/30 = 600/30 = 20. So C_{26} = 5 + 20/6 = 5 + 10/3 = 25/3 ≈ 8.333. C_{16} = 71/10 = 7.1. Difference = 25/3 - 71/10 = 250/30 - 213/30 = 37/30 ≈ 1.233. Differences: n=2:0, n=3:1/3=10/30, n=4:2/3=20/30, n=5:29/30, n=6:37/30. Not a simple pattern.

Maybe the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2/(something)? No.

Let's search my memory for the exact formula from Knuth's book. I recall that the average number of comparisons in quickselect (Hoare's FIND) is: C_{mn} = 2(n+1)H_n - 2(n+3-2m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? No.

Wait, I have a PDF of TAOCP Vol 3 in my mind. The answer to exercise 32 is likely: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But that gave 2 for n=2,m=1. Maybe the formula is for C_{mn} + 1? Or maybe the recurrence in the book is different: "For simplicity, let M = 1; that is, don't assume the use of a special technique for short subfiles." This might mean that when the subfile size is 1, we still do something? But M is usually the cutoff for using a different method (like insertion sort) for small subfiles. If M=1, we don't use any special technique, so we just use the same algorithm down to size 1. That's what we did.

Maybe the quickfind method in exercise 31 is not exactly Hoare's FIND but a variant? Exercise 31: "Suppose that, instead of sorting an entire file, you only want to determine the mth smallest of n elements. Show that quicksort can be adapted to this purpose, avoiding many of the computations required to do a complete sort." So it's exactly quickselect.

Let's check the values in the book's answers. I can try to recall: In the answer to exercise 32, Knuth gives: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? And then says the asymptotic behavior for the median is something like 2n + o(n)? Wait, the average number of comparisons for median finding is ~ (2 + 2 ln 2)n? Actually, the constant for median finding is about 3.39n? Let's compute: For median, m = (n+1)/2. The leading term is 2n? Or something else? For quickselect, the average number of comparisons to find the median is ~ (2 + 2 ln 2)n ≈ 3.386n? Wait, I recall that the expected number of comparisons for quickselect to find the median is ~ (2 + 2 ln 2)n ≈ 3.386n. For min/max it's ~ 2n. For general m, it's ~ 2n + O(log n)? Actually, for fixed m (like min), it's 2n - 2 log n + O(1). For median, it's larger.

Let's check: C_{1n} ~ 2n - 2 ln n. So leading term 2n. If median has leading term c n, what is c? The recurrence for the continuous limit gives an integral equation. The expected number of comparisons for quickselect with random pivot to find the median is known to be ~ (2 + 2 ln 2)n ≈ 3.386n. Yes, that's a classic result. So C_{mn} for m ~ n/2 is ~ 3.386n.

Now, if the formula C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 gave 2 for n=2,m=1, then for large n, m=1, it would be ~ 2n ln n? Let's check asymptotics of that formula for m=1: 2n ln n - 2n ln n - 220? Wait, H_n ~ ln n + gamma. H_{n-m+1} = H_n ~ ln n. Then 2(n+1)H_n - 2(n+1)H_n - 4H_1 + 2n + 2 = 2n + constant. So it would give ~2n for m=1. That matches C_{1n} ~ 2n. But our exact C_{1n} = 2n - 2H_n, which is 2n - 2 ln n - 2gamma + o(1). The formula 2(n+1)H_n - 2(n+1)H_n - 4 + 2n + 2 = 2n - 2. That's 2n - 2, not 2n - 2H_n. So it's off by -2H_n + 2? For m=1, the formula gives 2n - 2, but we have 2n - 2H_n. So the formula is missing a -2H_n + 2? Actually 2n - 2H_n = (2n - 2) - 2(H_n - 1). So it's different by a harmonic term.

Maybe the correct formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2H_n? That would be 2n H_n? No.

Let's derive the exact formula properly.

We have recurrence: n C_{mn} = n(n-1) + sum_{j=1}^{m-1} C_{j, n-m+j} + sum_{j=m}^{n-1} C_{m, j}.

Let's try to find a telescoping sum by considering the difference C_{m,n} - C_{m,n-1} or something.

Another approach: The expected number of comparisons can be expressed as sum over all elements of the probability that they are compared. In quickselect, we partition subarrays that contain the m-th element. The comparisons are exactly those that occur in quicksort restricted to the subarray that contains the m-th element? Actually, quickselect does the following: pick a pivot, compare it with all other elements in the current subarray. If the pivot's rank is k, and m < k, we recurse on the left subarray (elements < pivot). The elements in the left subarray are exactly those that were compared with the pivot and found smaller. In the next step, we pick a new pivot from that left subarray and compare it with all other elements in that subarray. So the set of comparisons is exactly the set of comparisons in quicksort that involve only elements that are in the same "ancestral" subarrays as the m-th element. This is equivalent to: we run quicksort, but we only partition subarrays that contain the m-th element. The total number of comparisons is the sum over all such partitions of (size of subarray - 1).

We can compute the expected number by considering each pair of elements (i, j) and determining if they are compared. In quickselect, two elements are compared if and only if one of them is chosen as a pivot while the other is in the same subarray, and the subarray contains the m-th element. This is a known analysis.

Let the elements be ranked 1,2,...,n. We want the m-th smallest. In quickselect, we only process subarrays that contain the m-th element. Consider two elements with ranks a and b (a < b). They are compared if and only if the first pivot chosen from the interval [a, b] is either a or b, AND the subarray containing the m-th element at that time includes both a and b. But since we only process subarrays containing m, the condition is that the interval [a, b] contains m, and the first pivot chosen from [a, b] is either a or b. Because if m is not in [a, b], then a and b will never be in the same subarray that contains m (since the subarray containing m will either be entirely to the left of a or entirely to the right of b, or contain both a and b? Actually, if m is not in [a, b], then a and b are both on the same side of m. In quickselect, we only recurse on the side that contains m. So we will never process a subarray that contains both a and b if they are both on the side not containing m? Wait: The initial array contains all elements. We pick a pivot. If the pivot is not m, we recurse on the subarray that contains m. That subarray will contain m and all elements between the pivot and m? Actually, if pivot is k < m, we recurse on the right subarray (elements > pivot). That subarray contains all elements with rank > k. Since m > k, it contains m, a, b if a,b > k. So if both a and b are > k, they remain together. So it's possible that a and b are on the same side of m and still get compared? Let's think: In quickselect, we only ever partition subarrays that contain the m-th element. So we start with the whole array (contains m). We pick a pivot. If pivot < m, we discard left subarray (elements < pivot) and recurse on right subarray (elements > pivot). The right subarray still contains m. So we only ever keep subarrays that contain m. Therefore, two elements a and b will be in the same subarray at some point if and only if the subarray containing m also contains both a and b. Since we only keep subarrays containing m, this means that a and b are compared if and only if they are in the same subarray that contains m, and one of them is chosen as pivot before the other is separated from m? Actually, the process: we have a subarray containing m. We pick a pivot uniformly from that subarray. We compare the pivot with all other elements in the subarray. So the pivot is compared with all other elements in that subarray. Then we discard one side and keep the side containing m. So two elements a and b are compared if and only if at some point one of them is the pivot and the other is in the same subarray. This happens if and only if the first element chosen as a pivot from the set of elements that are in the same subarray as m and also include both a and b is either a or b. The subarray containing m at any step is an interval of ranks that contains m. So the process is: we have an interval [L, R] containing m. We pick a pivot k uniformly from [L, R]. We compare k with all other elements in [L, R]. Then we set either L = k+1 (if k < m) or R = k-1 (if k > m). We stop when k = m. So two elements a and b (a < b) are compared if and only if at some step, the interval [L, R] contains both a and b, and the pivot chosen is either a or b, and this is the first pivot chosen from the set of elements that are in the interval containing both a and b? Actually, the first pivot chosen from the interval [a, b] that also contains m? Since the interval always contains m, and we only shrink it by moving L or R, the first pivot chosen from the set of elements that are in the current interval and also in [a, b] will be the first pivot chosen from the intersection of the current interval and [a, b]. But the current interval always contains m, so it contains [a, b] if and only if m is in [a, b] or the interval extends beyond [a, b] to include m? Wait, if m is not in [a, b], say a < b < m. Then the initial interval [1, n] contains a, b, m. The first pivot chosen from [a, b]? But we only pick pivots from the current interval, which always contains m. The elements a and b are in the current interval as long as the interval's left bound L <= a. The process continues until the pivot equals m. The pivots are chosen from the current interval. The first pivot that falls in [a, b] will be compared with all other elements in the current interval, including the other of a, b. So a and b are compared if the first pivot chosen from [a, b] is either a or b. But is it guaranteed that a pivot from [a, b] is ever chosen? The process stops when m is chosen. If m is chosen before any element from [a, b] is chosen, then a and b are never compared because the algorithm terminates. So a and b are compared iff the first pivot chosen from the set {a, b} ∪ {m? Actually, the set of elements that are candidates for being the first pivot from [a, b] is the set of all elements in the current interval that are in [a, b]? But the current interval shrinks. The first element chosen as pivot from the set of elements that are in the current interval and also in [a, b] is the first element from [a, b] that is chosen as pivot before m is chosen. Since the pivots are chosen uniformly from the current interval, the probability that a and b are compared is the probability that, in the random process of selecting pivots from intervals containing m, the first pivot chosen from the set [a, b] is either a or b.

This is equivalent to: In the set of all elements, we repeatedly pick a pivot uniformly from the current interval containing m, and we stop when we pick m. The order in which elements are picked as pivots (from the set of all elements) is a random permutation, but with the constraint that we only pick from the current interval? Actually, the sequence of pivots chosen is exactly the sequence of pivots that would be chosen in quicksort if we only sorted the subarray containing m? There's a known result: The probability that two elements a and b are compared in quickselect is:

If m is between a and b (i.e., a < m < b), then they are compared if and only if the first pivot chosen from [a, b] is a or b. Since m is in [a, b], the process will definitely pick a pivot from [a, b] before picking m? Not necessarily; m could be picked first. But if m is picked first, the algorithm stops and a and b are not compared. So the condition is that the first pivot chosen from [a, b] is a or b. The probability that the minimum element in a random permutation of [a, b] is either a or b is 2/(b-a+1). But wait, the order of pivots is not a random permutation of all elements? In quicksort, the pivots are chosen in a way that is equivalent to a random permutation: the first pivot is uniform from all n, then recursively. The set of pivots chosen in quicksort is a random permutation. In quickselect, we only choose pivots from intervals containing m, but the relative order of pivots from a set that always stays together? Actually, the process of quickselect is equivalent to: we pick a random permutation of the n elements, and we look at the first element in that permutation that is in the interval containing m? There's a known lemma: In Hoare's FIND, the probability that two elements a and b are compared is 2/(b-a+1) if m is between a and b, and 0 if both are on the same side of m? Let's test with a=1, b=2, m=2 (finding 2nd smallest of n). Then a=1, b=2, m=2. Here m is not strictly between a and b; b = m. In this case, are 1 and 2 compared? We want the 2nd smallest. If the pivot is 1 (min), then we compare 1 with all others, so 1 and 2 are compared. If pivot is 2, we compare 2 with all others, so 1 and 2 are compared. If pivot is >2, we compare pivot with all, so 1 and 2 are not compared with each other (they are both compared with pivot, but not with each other). Then we recurse on left subarray which contains 1 and 2? Wait, if pivot > m, say pivot=3, then we recurse on left subarray which contains 1,2. Then we pick a new pivot from {1,2}. That pivot will be either 1 or 2, and they will be compared. So in all cases, 1 and 2 are compared? Let's check n=3, m=2. Elements {1,2,3}. Pivot choices:
Pivot=1: compare 1 with 2,3. 1 and 2 compared. Then recurse on right subarray {2,3} to find 1st smallest (since m=2, m-k=1). In {2,3}, pivot could be 2: compare 2 with 3. 2 and 3 compared. Or pivot=3: compare 3 with 2. So 1 and 2 are compared.
Pivot=2: compare 2 with 1,3. 1 and 2 compared. Done.
Pivot=3: compare 3 with 1,2. 1 and 2 not compared directly. Then recurse on left subarray {1,2} to find 2nd smallest. In {1,2}, pivot is 1 or 2. If pivot=1: compare 1 with 2. 1 and 2 compared. If pivot=2: compare 2 with 1. 1 and 2 compared. So 1 and 2 are always compared. Probability = 1. Formula 2/(b-a+1) = 2/2 = 1. Works. Now consider a=2, b=3, m=2. 2/(2)=1. Are 2 and 3 always compared? In n=3,m=2: pivot=1: recurse on {2,3}, they are compared. pivot=2: compare 2 with 3. pivot=3: compare 3 with 2. So always compared. Probability 1. Now consider a=1, b=3, m=2. b-a+1=3. Probability 2/3? Let's check n=3,m=2. Are 1 and 3 compared? Pivot=1: compare 1 with 3? Yes, 1 is pivot, compared with 3. Pivot=2: compare 2 with 1,3. 1 and 3 not compared. Pivot=3: compare 3 with 1,2. 1 and 3 compared. So probability 2/3. Matches 2/3. Now consider a=1, b=2, m=3 (finding max of 3). Here both are on same side of m (left). Are they compared? Pivot choices: 1,2,3.
Pivot=1: compare 1 with 2,3. 1 and 2 compared. Then recurse on right {2,3} to find 2nd smallest? Wait m=3, pivot=1 < m, recurse on right {2,3} to find 2nd smallest (m-k=2). In {2,3}, we find 2nd smallest (which is max of {2,3}). That will compare 2 and 3. So 1 and 2 compared.
Pivot=2: compare 2 with 1,3. 1 and 2 compared. Then recurse on right {3} to find 1st smallest? m=3, k=2, m-k=1. {3} size 1, no comparisons. So 1 and 2 compared.
Pivot=3: compare 3 with 1,2. 1 and 2 not compared. Done. So probability 2/3. But according to the "m between a and b" rule, m=3 is not between 1 and 2. So probability is not 2/(b-a+1)? Here it is 2/3 anyway. What about a=2,b=3,m=1 (finding min)? Both on right side. Probability? Pivot=1: compare 1 with 2,3. 2 and 3 not compared. Pivot=2: compare 2 with 1,3. 2 and 3 compared. Pivot=3: compare 3 with 1,2. 2 and 3 compared. Probability 2/3. So for elements on the same side of m, probability is also 2/(b-a+1)? But wait, if m=2, a=1,b=3? That's m between. We got 2/3. If m=1, a=2,b=3? 2/3. If m=3, a=1,b=2? 2/3. So it seems for any a,b, the probability they are compared is 2/(|a-b|+1)? Let's test n=4, m=2, a=1,b=4. |1-4|+1=4. Probability 1/2? Let's check manually? Might be 1/2. But if that's true for all pairs, then the expected number of comparisons would be sum_{a<b} 2/(b-a+1) = sum_{d=1}^{n-1} 2/(d+1) * (n-d) = 2(n+1)H_n - 4n + 2? That's the quicksort comparisons! But quickselect comparisons are much smaller than quicksort. For n=3, quicksort comparisons average = 8/3? Actually quicksort average comparisons = 2(n+1)H_n - 4n. For n=3: 2411/6 - 12 = 88/6 - 12 = 14.667 - 12 = 2.667? Wait 88/6=14.666, minus 12 = 2.666? That's the average number of comparisons for quicksort? No, quicksort average comparisons is ~ 2n ln n. For n=3, exact is 8/3? Let's compute: 2411/6 - 43 = 88/6 - 12 = 14.666 - 12 = 2.666. But quicksort on 3 elements: min comparisons? The average number of comparisons in quicksort is indeed 8/3 for n=3? Let's check: quicksort with random pivot: comparisons for n=3: if pivot is 2, then compare 2 with 1 and 3 (2 comparisons), then sort {1} and {3} (0). Total 2. If pivot is 1, compare 1 with 2,3 (2), then sort {2,3} which takes 1 comparison (compare 2 and 3). Total 3. If pivot is 3, similarly 3. Average = (2+3+3)/3 = 8/3 ≈ 2.667. So quicksort average comparisons = 2(n+1)H_n - 4n? For n=3: 24*11/6 - 12 = 88/6 - 12 = 14.666 - 12 = 2.666. Yes. So sum_{a<b} 2/(b-a+1) = 2(n+1)H_n - 4n? Let's check: sum_{d=1}^{n-1} (n-d)*2/(d+1) = 2 sum_{d=1}^{n-1} (n-d)/(d+1) = 2 sum_{k=2}^{n} (n+1-k)/k = 2[(n+1)H_n - n - H_n + 1]? Actually sum_{k=2}^n (n+1-k)/k = (n+1) sum_{k=2}^n 1/k - sum_{k=2}^n 1 = (n+1)(H_n - 1) - (n-1) = (n+1)H_n - n - 1 - n + 1 = (n+1)H_n - 2n. Times 2 = 2(n+1)H_n - 4n. Yes.

But our quickselect average comparisons for n=3,m=2 is 8/3, which is exactly the quicksort average! For n=3,m=1, quickselect is 7/3 ≈ 2.333, which is less than quicksort 8/3. So the probability that two elements are compared in quickselect is not simply 2/(b-a+1) for all pairs. It depends on m.

Let's analyze the probability that a and b are compared in quickselect for general m. In quickselect, we only process subarrays that contain m. Two elements a and b are compared if and only if the first pivot chosen from the set of elements that are in the current subarray (which always contains m) and also in the interval between a and b is either a or b. But since the current subarray always contains m, if m is not between a and b, then a and b are on the same side of m. In that case, the subarray containing m will also contain a and b as long as we haven't discarded that side. We discard elements only when the pivot is on the side of m opposite to a and b? Actually, if a and b are both less than m, they are in the left side. The algorithm only discards the right side when pivot > m? Wait: If pivot > m, we recurse on left subarray (which contains m and all elements < pivot). Since a,b < m < pivot, they remain in the left subarray. If pivot < m, we recurse on right subarray (elements > pivot). Since a,b < m, they might be discarded if pivot > a,b? If pivot is between a and b? Let's think: The current interval is [L, R] containing m. If we pick a pivot k < m, we discard left part [L, k-1] and keep [k+1, R]. So elements less than k are discarded. If a and b are both less than m, they could be discarded if the pivot is greater than them? No, if pivot k < m, we keep elements > k. So if a and b are both > k, they remain. If one of them is < k, it gets discarded. But we only care if they are compared before being separated. They are compared if one of them is chosen as pivot while the other is still in the interval. This is equivalent to: in the random permutation of the elements, the first element from the set {a, b} ∪ {elements that separate them from m}? Actually, there's a known result: In quickselect, the probability that two elements with ranks a and b are compared is:

2/(b-a+1) if m is in [a, b] (i.e., a <= m <= b).
0 if a < b < m or m < a < b? But we saw for n=3,m=2, a=1,b=2? Here m=2 is in [1,2], so probability 2/2=1. For a=2,b=3, m=2 in [2,3], probability 1. For a=1,b=3, m=2 in [1,3], probability 2/3. For n=3,m=1, a=2,b=3: m=1 not in [2,3]. According to the rule, probability 0. But we observed probability 2/3 for n=3,m=1, a=2,b=3? Let's re-check n=3,m=1 (finding min). Elements 1,2,3. We want 1. Pivot=1: compare 1 with 2,3. 2 and 3 not compared. Pivot=2: compare 2 with 1,3. 2 and 3 compared? Yes, 2 is pivot, compared with 3. Then we recurse on left subarray {1} (since k=2 > m=1). Done. So 2 and 3 compared. Pivot=3: compare 3 with 1,2. 2 and 3 compared. Then recurse on left {1,2}. In {1,2}, we find min. Pivot=1: compare 1 with 2. 2 and 3 not compared again. Pivot=2: compare 2 with 1. 2 and 3 not compared. So in the case pivot=3, 2 and 3 are compared in the first partition. So overall, 2 and 3 are compared in 2 out of 3 cases? Pivot=1: not compared. Pivot=2: compared. Pivot=3: compared. So probability 2/3. But according to the rule "m not in [a,b] => 0", that would be wrong. So the rule is not that simple.

Let's re-analyze the process for a=2,b=3,m=1. The algorithm only processes subarrays that contain m=1. The initial array is {1,2,3}. If pivot=1, algorithm stops. 2 and 3 are not compared. If pivot=2, we compare 2 with 1 and 3. So 2 and 3 are compared. Then since pivot=2 > m, we recurse on left subarray {1}. The subarray {1} does not contain 2 or 3. So 2 and 3 are compared in this case. If pivot=3, we compare 3 with 1 and 2. So 2 and 3 are compared. Then we recurse on left subarray {1,2}. Now we process {1,2} to find min. In {1,2}, we compare the pivot with the other element. If pivot=1, we compare 1 with 2 (2 and 3 not involved). If pivot=2, we compare 2 with 1 (2 and 3 not involved). So 2 and 3 were compared in the first step. So indeed 2 and 3 are compared with probability 2/3.

So the probability that a and b are compared depends on whether the algorithm ever picks a pivot from the set of elements that are between a and b? Actually, the algorithm always picks pivots from the current interval containing m. The first pivot chosen from the set of elements that are in the current interval and also in the interval between a and b? But the current interval always contains m. If m is not between a and b, then the interval between a and b does not contain m. However, the current interval contains m, so it extends beyond [a,b] to include m. The first pivot chosen from [a,b] will be compared with all other elements in the current interval, including the other of a,b. But will a pivot from [a,b] ever be chosen? The algorithm stops when m is chosen. If m is chosen before any element from [a,b], then no pivot from [a,b] is chosen, and a and b are never compared. If an element from [a,b] is chosen before m, then that pivot is compared with the other element (since the other is in the current interval). So the probability that a and b are compared is the probability that the first element chosen as pivot from the set {a, b} ∪ {m}? Not exactly, because the current interval shrinks. The elements that are chosen as pivots are a subset of the elements. The process is equivalent to: we randomly permute all elements. We then look at the elements in the order of the permutation. We start with the whole set. The first element in the permutation that belongs to the current interval containing m is chosen as pivot. Then we restrict the interval to the side containing m. This is exactly the process of building a random binary search tree for the elements, but only following the path to m. The set of pivots chosen is exactly the set of elements that are ancestors of m in the random BST? Actually, in quicksort, the pivots are the nodes of the random BST. In quickselect, we only choose pivots along the path from the root to m. The comparisons performed are exactly the comparisons that involve these pivots and the elements in their respective subtrees that are on the path to m? Wait, in quickselect, when we pick a pivot, we compare it with all other elements in the current subarray. The current subarray is exactly the set of elements in the subtree of that pivot that contains m. So the comparisons are all pairs (pivot, x) where x is in the subtree of the pivot that contains m, and x is not the pivot. This is equivalent to: for each element x ≠ m, x is compared with all its ancestors on the path from the root to m? Actually, in the random BST, the path from root to m consists of a sequence of nodes. The comparisons are exactly the pairs (u, v) where u is on the path to m and v is in the subtree of u that contains m (and v ≠ u). This is exactly the set of pairs (u, v) such that u is an ancestor of m and v is a descendant of u in the direction of m? More precisely, in the random BST, the comparisons in quickselect are all pairs (x, y) such that x is on the path from root to m, and y is in the subtree of x that contains m, and y ≠ x. The total number of comparisons is sum over nodes x on the path to m of (size of subtree of x containing m - 1). The expected value of this sum can be computed.

There is a known formula for the expected number of comparisons in quickselect (Hoare's FIND) by Knuth. I recall it is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But that gave 2 for n=2,m=1. Let's check the values from that formula for n=2,m=1: 231.5 = 9. -2*(2+2-1)= -23= -6 * H_2= -9. -2(1+1)*H_1= -4. +2n+2=6. Total = 9-9-4+6=2. But we think C12=1. Could it be that the algorithm in the book does an extra comparison? Let's read the description of quickfind in exercise 31. "Show that quicksort can be adapted to this purpose, avoiding many of the computations required to do a complete sort." In quicksort, the partitioning might use n+1 comparisons? Or maybe the algorithm checks if the subfile size is 1 and does a comparison? But M=1 means no special technique for short subfiles, so for size 1 we don't do anything? In quicksort, when the subfile size is 1, we don't partition. So no comparisons. So C11=0.

Maybe the formula is C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n? For n=2,m=1: 9 - 9 - 4 + 4 = 0. Not 1.

Maybe the formula is C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n-m+1} - 2(m+1)H_m + 2n? n=2,m=1: 9 - 221.5=9-6=3 -4= -1 +4=3. No.

Let's search for the exact formula in known literature. The average number of comparisons for Hoare's FIND is: C_{mn} = 2(n+1)H_n - 2(n+3-2m)H_{n-m+1} - 2(m+1)H_m + something? No.

I can derive it from the recurrence using generating functions or by solving the difference equation.

Let's write the recurrence for C_{mn} in a more symmetric form. Define for 1 <= m <= n: n C_{mn} = n(n-1) + sum_{i=1}^{m-1} C_{m-i, n-i} + sum_{i=m+1}^{n} C_{m, i-1}.

Consider the function F(m,n) = C_{mn} + 2? Maybe it simplifies.

Let's compute the values of C_{mn} + something to see if they match a known pattern.

We have: C_{1n} = 2n - 2H_n. C_{2n} = ? Let's find an expression for C_{2n} from the recurrence. For m=2: n C_{2n} = n(n-1) + C_{1, n-1} + sum_{i=3}^{n} C_{2, i-1}. But C_{1, n-1} = 2(n-1) - 2H_{n-1}. And sum_{i=3}^{n} C_{2, i-1} = sum_{j=2}^{n-1} C_{2j}. So n C_{2n} = n(n-1) + 2n - 2 - 2H_{n-1} + sum_{j=2}^{n-1} C_{2j}. Let S_n^{(2)} = sum_{j=2}^{n} C_{2j}. Then sum_{j=2}^{n-1} C_{2j} = S_{n-1}^{(2)}. And n C_{2n} = n S_n^{(2)} - (n-1) S_{n-1}^{(2)}? Actually C_{2n} = S_n^{(2)} - S_{n-1}^{(2)}. So n (S_n^{(2)} - S_{n-1}^{(2)}) = n(n-1) + 2n - 2 - 2H_{n-1} + S_{n-1}^{(2)}. n S_n^{(2)} - n S_{n-1}^{(2)} = n^2 - n + 2n - 2 - 2H_{n-1} + S_{n-1}^{(2)}. n S_n^{(2)} = (n+1) S_{n-1}^{(2)} + n^2 + n - 2 - 2H_{n-1}. Divide by n(n+1): S_n^{(2)}/(n+1) = S_{n-1}^{(2)}/n + (n^2+n-2-2H_{n-1})/(n(n+1)). Simplify (n^2+n-2) = (n+2)(n-1). So (n+2)(n-1)/(n(n+1)) = (n+2)/n * (n-1)/(n+1)? Not a simple telescoping.

Maybe there's a known closed form: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? Let's test for n=4,m=2. H_4=25/12, H_3=11/6, H_2=3/2. 2525/12 = 250/12 = 125/6 ≈ 20.833. -2*(4+2-2)= -24= -8 * H_3 = -811/6 = -88/6 = -14.667. -2*(2+1)H_2 = -61.5 = -9. +2n+2=10. Sum = 125/6 - 88/6 - 9 + 10 = 37/6 +1 = 43/6 ≈ 7.167. But C24=9/2=4.5. So that's way off.

Maybe the formula is C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n-m+1} - 2(m+1)H_m + 2n? n=4,m=2: 125/6 - 2311/6 = 125/6 - 66/6 = 59/6 ≈9.833 - 9 = 59/6 - 9 = 59/6 - 54/6 = 5/6? +8? Wait 2n=8. So 5/6+8=53/6≈8.833. No.

Let's try to find the formula by assuming it's a linear combination of harmonic numbers and n. Since the recurrence is linear, we can try to find coefficients.

We have symmetry: C_{mn} = C_{n+1-m, n}. So the formula should be symmetric under m -> n+1-m.

Let's write the recurrence in terms of D_{mn} = C_{mn} - C_{m-1,n} for m>1, and C_{1n} known.

Alternatively, we can use the approach from "The Art of Computer Programming" where they solve this exact recurrence. I recall that in the answer to exercise 32, Knuth gives: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But that didn't match. Let me check the values for n=3,m=2 again. Maybe my C23 is wrong? Let's recompute C23 from the definition of quickfind.

Exercise 31: "Suppose that, instead of sorting an entire file, you only want to determine the mth smallest of n elements. Show that quicksort can be adapted to this purpose, avoiding many of the computations required to do a complete sort." The algorithm: Pick a pivot, partition the array. If pivot is the mth, done. Else if pivot index > m, recurse on left part. Else recurse on right part with adjusted m.

In the analysis, the number of comparisons for partitioning n elements is n-1 (comparing pivot with each other element). This is standard.

But maybe the book uses a different partitioning scheme? In some versions of quicksort, the partitioning uses n comparisons because the pivot is compared with all n elements including itself? No.

Wait, in the MIX program for quicksort (Algorithm Q) in Section 5.2.2, the partitioning might do n comparisons? Let's check the context. The section is 5.2.2, and the preceding exercises are 29,30,31. Exercise 31 is about quickfind. The analysis of quicksort in this section uses the number of comparisons C = n-1 for partitioning? Actually, in the analysis of bubble sort, they use comparisons. For quicksort, the standard analysis uses n+1 comparisons? I need to recall the exact analysis in TAOCP.

In TAOCP Vol 3, Section 5.2.2, the analysis of quicksort (Algorithm Q) is given. The number of comparisons in quicksort is analyzed in Section 5.2.2? Actually, the analysis of quicksort is in Section 5.2.2? The text says "partition exchange (Hoare's 'quicksort')" and then they discuss bubble sort. The analysis of quicksort might be in a later section? Wait, the section is 5.2.2 "Sorting by Exchanging". It covers bubble sort, then merge exchange, partition exchange (quicksort), and radix exchange. The analysis of quicksort might be in the exercises or in the text. I see the text provided includes only bubble sort analysis. The exercise 31 is about quickfind, which is based on quicksort. So the recurrence for comparisons in quickfind should be the same as in quicksort but only on one side.

In the standard analysis of quicksort in Knuth's book, the number of comparisons for partitioning n elements is n+1? Let me check: In quicksort, the partitioning step often uses a sentinel or compares indices. In Knuth's Algorithm Q (Program Q), the inner loop does a comparison for each element. I think the number of comparisons is n-1 for partitioning n elements? Actually, in the standard quicksort partition (Hoare's original), the number of comparisons is n+1? Let's recall: In Hoare's partition, you have two pointers i and j, you move i right while A[i] < pivot, and j left while A[j] > pivot. Each comparison of A[i] with pivot and A[j] with pivot counts. The total comparisons can be n+1 in some versions. But in the analysis of quicksort in Knuth, the average number of comparisons is 2(n+1)H_n - 4n. That formula corresponds to partitioning cost of n+1? Let's check: If partitioning cost is n+1, then recurrence for quicksort comparisons C_n = n+1 + (2/n) sum_{k=1}^{n-1} C_k. The solution is C_n = 2(n+1)H_n - 4n. For n=3, C_3 = 2411/6 - 12 = 88/6 - 12 = 2.666. If partitioning cost is n-1, then C_n = n-1 + (2/n) sum C_k. For n=3: C_3 = 2 + (2/3)(C_1+C_2). C_1=0, C_2=1 (if cost 1). Then C_3 = 2 + (2/3)1 = 8/3 = 2.666. So both give same for n=3? Let's check n=2: if cost n-1=1, C_2 = 1 + (2/2)C_1 = 1. If cost n+1=3, C_2 = 3 + C_1 = 3. The standard quicksort average comparisons is 2(n+1)H_n - 4n. For n=2: 231.5 - 8 = 9 - 8 = 1. So partitioning cost is n-1? 2(n+1)H_n - 4n for n=2 gives 1. So the recurrence with n-1 gives C_2=1. With n+1 gives 3. So Knuth uses partitioning cost n-1? But the formula 2(n+1)H_n - 4n is derived from recurrence C_n = n+1 + (2/n) sum_{k=1}^{n-1} C_k? Let's check: If C_n = n+1 + (2/n) sum C_k, then for n=2: C_2 = 3 + C_1 = 3. But 2(3)H_2 - 8 = 9-8=1. So that recurrence gives 3, not 1. So the recurrence for the standard formula 2(n+1)H_n - 4n is C_n = n-1 + (2/n) sum C_k? Let's solve: C_n = n-1 + (2/n) S_{n-1}. Then n C_n = n(n-1) + 2 S_{n-1}. S_n = S_{n-1} + C_n = S_{n-1} + n-1 + (2/n) S_{n-1} = (1+2/n) S_{n-1} + n-1. This is the same recurrence as for C_{1n} in quickselect! And we solved it to get S_n = (n+1)(n+2 - 2H_{n+1})? Wait, we solved for C_{1n} which had recurrence n C_{1n} = n(n-1) + S_{n-1} (with S_{n-1} = sum C_{1j}). That gave C_{1n} = 2n - 2H_n. For quicksort, the recurrence is n C_n = n(n-1) + 2 S_{n-1}. That would give C_n = 2 * (2n - 2H_n)? Actually, if we multiply the C_{1n} recurrence by 2? n C_{1n} = n(n-1) + S_{n-1}. For quicksort, n C_n = n(n-1) + 2 S_{n-1}. So C_n = 2 C_{1n}? Then C_n = 4n - 4H_n. But the known quicksort average is 2(n+1)H_n - 4n. For n=3: 43 - 411/6 = 12 - 44/6 = 12 - 7.333 = 4.667, not 2.667. So that's not it.

Let's re-derive quicksort recurrence carefully. In quicksort, we partition n elements. The number of comparisons in partitioning is often n+1 in Knuth's analysis? I need to check the exact text. In TAOCP Vol 3, Section 5.2.2, the analysis of quicksort is not in the provided text. The provided text is only about bubble sort. The exercises 29,30,31 are about other things. Exercise 29 is about Singleton's median of three. Exercise 30 about multiword keys. Exercise 31 about quickfind. So the quicksort analysis might be in a different section, but the recurrence for quickfind should be based on the same partitioning cost.

Maybe the partitioning cost in Hoare's quicksort is n+1 comparisons? Let's check Hoare's original partition algorithm. In Hoare's partition, you have two indices i and j, you move i right while A[i] < pivot, and j left while A[j] > pivot. The comparisons are: for each increment of i, you compare A[i] with pivot; for each decrement of j, you compare A[j] with pivot. The total comparisons is n+1 in the worst case? Actually, it can be n+1 because you might compare the pivot with itself? I'm not sure.

But the formula for quickselect average comparisons is well-known. I can look it up in my mental database. The expected number of comparisons to find the m-th smallest in a set of n distinct elements using Hoare's FIND is: C_{mn} = 2(n+1)H_n - 2(n+3-2m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? No.

I recall a paper by Mahmoud, "On the average number of comparisons in Hoare's FIND". The formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But that didn't match.

Wait, maybe the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? Let's test with n=4,m=2 again. I got 43/6 ≈ 7.167. But my computed C24 was 9/2 = 4.5. Could my C24 be wrong? Let's recompute C24 carefully using the recurrence.

C_{mn} = n-1 + (1/n)[sum_{k=1}^{m-1} C_{m-k, n-k} + sum_{k=m+1}^{n} C_{m, k-1}].

For n=4, m=2: C_{24} = 3 + (1/4)[ sum_{k=1}^{1} C_{2-1, 4-1} + sum_{k=3}^{4} C_{2, k-1} ]. k=1: C_{1,3} = 7/3. k=3: C_{2,2} = 1. k=4: C_{2,3} = 8/3. Sum = 7/3 + 1 + 8/3 = 7/3 + 3/3 + 8/3 = 18/3 = 6. C_{24} = 3 + 6/4 = 3 + 1.5 = 4.5. That seems correct.

Now, what does the formula 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 give for n=4,m=2? H_4 = 25/12, H_3 = 11/6, H_2 = 3/2. 2525/12 = 250/12 = 125/6 ≈ 20.833. -2*(4+2-2)= -24= -8 * H_3 = -811/6 = -88/6 ≈ -14.667. -2*(2+1)H_2 = -61.5 = -9. +2*4+2=10. Total = 125/6 - 88/6 - 9 + 10 = 37/6 + 1 = 43/6 ≈ 7.167. Not 4.5.

What about the formula: C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n-m+1} - 2(m+1)H_m + 2n? n=4,m=2: 2525/12 = 125/6. -2*(4+1-2)= -23= -6 * H_3 = -611/6 = -11. -231.5 = -9. +8. Total = 125/6 - 20 + 8 = 125/6 - 12 = 125/6 - 72/6 = 53/6 ≈ 8.833. No.

Maybe the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n? n=4,m=2: 125/6 - 88/6 - 9 + 8 = 37/6 - 1 = 31/6 ≈ 5.167. No.

Maybe it's: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2/(something)? No.

Let's search for the correct formula by solving the recurrence generally.

We have: n C_{mn} = n(n-1) + sum_{j=1}^{m-1} C_{j, n-m+j} + sum_{j=m}^{n-1} C_{m, j}. (1)

Let's define a function F(m,n) = C_{mn} + a n + b H_n + c m + d H_m + e H_{n-m+1} + ... but maybe we can find a telescoping form by considering the difference with respect to n.

Consider the recurrence for C_{m,n} and C_{m,n-1}: n C_{mn} = n(n-1) + sum_{j=1}^{m-1} C_{j, n-m+j} + sum_{j=m}^{n-1} C_{m, j}. (n-1) C_{m,n-1} = (n-1)(n-2) + sum_{j=1}^{m-1} C_{j, n-1-m+j} + sum_{j=m}^{n-2} C_{m, j}.

Subtract: n C_{mn} - (n-1) C_{m,n-1} = 2n-2 + sum_{j=1}^{m-1} [C_{j, n-m+j} - C_{j, n-m-1+j}] + C_{m, n-1}.

Let d = n-m. Then n-m+j = d+j. n-m-1+j = d-1+j. So the sum is over j=1 to m-1 of [C_{j, d+j} - C_{j, d-1+j}].

This is the difference in the second argument for fixed first argument. If we define D_{a,b} = C_{a,b} - C_{a,b-1} (for b>a?), then the sum is sum_{j=1}^{m-1} D_{j, d+j}.

But we also have a recurrence for C_{m,n} in terms of C_{m-1,n}? Let's try that. m C_{mn}? Not symmetric.

Another approach: The problem is equivalent to finding the expected number of comparisons in a random BST on the path to the m-th node. There is a known result: The expected number of comparisons in Hoare's FIND is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? I'm quite sure I've seen this formula. Let me test it for n=5,m=3 (median of 5). n=5,m=3. H_5 = 137/60 ≈ 2.2833. H_3 = 11/6 ≈ 1.8333. H_3 = 11/6. Formula: 26137/60 = 12137/60 = 1644/60 = 27.4. -2(5+2-3)= -24= -8 * H_3 = -811/6 = -88/6 = -14.667. -2*(3+1)H_3 = -811/6 = -14.667. +25+2=12. Sum = 27.4 - 14.667 - 14.667 + 12 = 10.066. Asymptotically, for median, m ~ n/2, the formula gives ~ 2n ln n - 2(n/2) ln(n/2) - 2(n/2) ln(n/2) + 2n = 2n ln n - n ln(n/2) - n ln(n/2) + 2n = 2n ln n - 2n (ln n - ln 2) + 2n = 2n ln n - 2n ln n + 2n ln 2 + 2n = 2n(ln 2 + 1) ≈ 3.386n. That matches the known constant for median finding! 2(ln 2 + 1) ≈ 3.386. So the formula with 2n+2 gives the correct asymptotic for median! But for n=5,m=3, the exact value from the formula is 10.066? Let's compute exactly: 26H_5 = 12 * 137/60 = 1644/60 = 411/15 = 27.4. -8H_3 = -811/6 = -88/6 = -44/3 ≈ -14.6667. -8H_3 = -44/3. +12 = 12. Total = 411/15 - 88/3 + 12 = 411/15 - 440/15 + 180/15 = (411 - 440 + 180)/15 = 151/15 ≈ 10.0667. Now what is the actual C_{35}? We computed C_{35} = 101/15 ≈ 6.733. So the formula gives 151/15, which is 50/15 = 10/3 ≈ 3.333 more. So the formula overestimates by 10/3 for n=5,m=3.

But the asymptotic constant matches! So maybe the formula is correct for large n, but there is a missing term that is lower order? Or maybe the formula is exactly C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - something that vanishes for large n? But we need an exact closed form.

Let's check the formula for n=3,m=2: 2411/6 = 44/3 ≈ 14.667. -2*(3+2-2)= -23= -6 * H_2 = -9. -2(2+1)*H_2 = -9. +8. Total = 44/3 - 18 + 8 = 44/3 - 10 = 14/3 ≈ 4.667. Actual C23 = 8/3 ≈ 2.667. Difference = 2.

For n=4,m=2: formula 43/6 ≈ 7.167, actual 9/2=4.5. Difference = 43/6 - 27/6 = 16/6 = 8/3 ≈ 2.667.

For n=2,m=1: formula 2, actual 1. Difference = 1.

So the formula is consistently too high. Maybe the correct formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2H_n? No.

Let's try to find the exact formula by matching the values we have.

We have: C_{1n} = 2n - 2H_n. C_{2n}: n=2:1, n=3:8/3, n=4:9/2, n=5:32/5, n=6:25/3. Let's express C_{2n} in terms of n and H_n. C_{22}=1 = 4 - 3 = 22 - 2H_2. C_{23}=8/3 = 6 - 10/3 = 23 - 2H_3 + 2/3? 23 - 211/6 = 6 - 11/3 = 7/3. 8/3 = 7/3 + 1/3. C_{24}=9/2 = 8 - 7/2? 24 - 2H_4 = 8 - 25/6 = 23/6 ≈ 3.833. 9/2 = 27/6 = 23/6 + 4/6 = 23/6 + 2/3. C_{25}=32/5 = 6.4. 25 - 2H_5 = 10 - 274/60 = 600/60 - 274/60 = 326/60 = 163/30 ≈ 5.433. 32/5 = 192/30 = 163/30 + 29/30. C_{26}=25/3 = 8.333. 26 - 2H_6 = 12 - 2(137/60? Wait H_6 = 1+1/2+1/3+1/4+1/5+1/6 = 49/20 = 2.45. 2H_6 = 49/10 = 4.9. 12-4.9=7.1 = 71/10. 25/3 = 250/30 = 8.333. 71/10 = 213/30. Difference = 37/30.

So C_{2n} = 2n - 2H_n + d_n, where d_2=0, d_3=1/3, d_4=2/3, d_5=29/30, d_6=37/30. d_n = ? 1/3 = 10/30, 2/3=20/30, 29/30, 37/30. Not obvious.

Maybe we need to find the general formula by solving the recurrence with generating functions. I recall that the exact formula for C_{mn} is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2 \sum_{i=1}^{?} ... No.

Let's look at the recurrence again. Maybe I mis-copied the recurrence. In some versions of quickselect, the number of comparisons for partitioning is n, not n-1. If it's n, then the recurrence becomes: C_{mn} = n + (1/n)[sum...]. Then for n=2,m=1: C_{12} = 2. For n=3,m=1: C_{13} = 3 + (1/3)(C12) = 3 + 2/3 = 11/3 ≈ 3.667. But the problem says "For simplicity, let M = 1; that is, don't assume the use of a special technique for short subfiles." This might refer to a parameter M in quicksort that cuts off recursion for small subfiles. In quicksort, M is the size below which you use insertion sort. For quickfind, M=1 means you don't use any special technique, so you just recurse down to size 1. The partitioning cost is still n-1? Or maybe the standard quicksort in Knuth uses n+1 comparisons? I need to check the context of the book. In the provided text, they analyze bubble sort. The exercises 29,30,31 are separate. Exercise 31 says "Show that quicksort can be adapted to this purpose". It doesn't specify the exact number of comparisons. But the standard analysis of quicksort in Knuth's book (Section 5.2.2 or 5.2.3) might use a specific partitioning cost. I recall that in TAOCP Vol 3, the analysis of quicksort (Algorithm Q) gives the average number of comparisons as 2(n+1)H_n - 4n? Or is it 2n ln n + ...? Actually, in the summary of sorting algorithms at the end of Section 5.2, Knuth gives the average number of comparisons for quicksort as 2n ln n + O(n). But the exact formula might be different.

Wait, I remember that in the answer to exercise 32 (which I might have seen before), the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2. But we saw it doesn't match our small values. Could it be that the recurrence includes the comparison to check if the pivot is the desired element? That would add 1 per partition? But that's not a key comparison.

Maybe the "key comparisons" in quickfind include the comparisons made during partitioning, and the partitioning algorithm used is different. In Hoare's FIND, the partitioning might be done with two pointers and the number of comparisons is n+1? Let's check Hoare's original paper: "Algorithm 63 (PARTITION)" and "Algorithm 64 (QUICKSORT)" and "Algorithm 65 (FIND)". In Hoare's FIND, the partitioning is the same as quicksort. The number of comparisons in partitioning n elements is n+1? Actually, in Hoare's partition, you have two indices i and j, you do i++ while A[i] < pivot, and j-- while A[j] > pivot. The total number of comparisons is n+1 because you compare the pivot with itself? I'm not entirely sure.

Let's test the formula C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 with the assumption that the base case C_{11} = 0? For n=1, m=1: H_1=1. Formula: 221 - 2*(1+2-1)H_1 - 221 + 2+2 = 4 - 221 - 4 + 4 = 4 - 4 - 4 + 4 = 0. So base case works. For n=2,m=1: 23H_2 - 2(2+2-1)H_2 - 22H_1 + 6 = 61.5 - 6*1.5 - 4 + 6 = 9 - 9 - 4 + 6 = 2. So C_{12}=2. If the algorithm does 2 comparisons for n=2, that means partitioning cost is 2? For n=2, partitioning 2 elements: compare the two elements once? Or compare pivot with the other element once? That's 1 comparison. But if the algorithm does something else, maybe it's 2.

Let's check the recurrence if partitioning cost is n (instead of n-1). Then C_{1n} = n + (1/n) sum_{j=1}^{n-1} C_{1j}. Then n C_{1n} = n^2 + S_{n-1}. S_n = S_{n-1} + n + S_{n-1}/n = S_{n-1}(1+1/n) + n. S_1=0. S_2 = 0 + 2 = 2, C12=2. S_3 = 2*(4/3) + 3 = 8/3+3=17/3, C13=17/3-2=11/3≈3.667. S_4 = (17/3)*(5/4)+4 = 85/12+4=133/12≈11.083, C14=133/12-17/3=133/12-68/12=65/12≈5.417. The formula 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 for m=1 gives: 2(n+1)H_n - 2(n+1)H_n - 4 + 2n+2 = 2n - 2. For n=2: 2. For n=3: 4. But our recurrence with cost n gave C13=11/3≈3.667. Not 4. So that formula doesn't match cost n either.

What if partitioning cost is n+1? Then C_{1n} = n+1 + (1/n) S_{n-1}. n C_{1n} = n(n+1) + S_{n-1}. S_n = S_{n-1}(1+1/n) + n+1. S_2 = 3, C12=3. Formula for m=1: 2n+2-4=2n-2? For n=2:2. Not 3.

So the formula doesn't match a simple constant partitioning cost.

Maybe the formula is exactly: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2H_n? No.

Let's try to derive the correct formula by solving the recurrence properly. We have: n C_{mn} = n(n-1) + sum_{j=1}^{m-1} C_{j, n-m+j} + sum_{j=m}^{n-1} C_{m, j}.

This is a linear recurrence. We can try to find a solution of the form: C_{mn} = A_n + B_m + C_{n-m+1} + ... but the recurrence mixes indices.

Consider the function f(m,n) = C_{mn} + 2? Let's compute f(1,n) = 2n - 2H_n + 2? Not simpler.

Maybe we can use the approach of "recurrence for expectations" by considering the expected number of times an element is compared. In quickselect, each element is compared with pivots until it is either chosen as pivot or discarded (if it's on the wrong side of m). Actually, an element x is compared with a pivot if and only if the pivot is chosen from the current subarray containing m, and x is still in that subarray. The process stops when m is chosen. The elements that are compared are those that are in the same subarray as m at the time the pivot is chosen. This is equivalent to: we build a random BST, and we look at the path from root to m. The comparisons are all pairs (pivot, element) where pivot is on the path to m and element is in the subtree of pivot that contains m. The expected number of comparisons is the expected sum over nodes on the path to m of (size of that node's subtree in the direction of m - 1). This can be computed using the properties of random BSTs.

In a random BST of n nodes, the path from root to a specific node of rank m has a certain distribution. The expected number of comparisons can be derived by linearity of expectation: for each element x ≠ m, the expected number of times it is compared is the expected number of ancestors of m that are also ancestors of x? Actually, x is compared with a pivot y if y is an ancestor of m and x is in the subtree of y that contains m. This happens if and only if y is the first common ancestor of x and m? Or something like that.

I recall a known result: The expected number of comparisons in Hoare's FIND is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But we saw it doesn't match our small n. Could it be that the book uses a different definition of "key comparisons"? Maybe they count the comparison of the pivot with the target? No.

Let's check the values from the book's answer if possible. I can try to find the answer by reasoning about the recurrence solution.

We can solve the recurrence by using the "telescoping" trick with harmonic numbers. Let's try to find a function g(m,n) such that the recurrence becomes simple.

Define D_{mn} = C_{mn} - C_{m-1,n} for m>=2, and D_{1n} = C_{1n}. But maybe we can find a recurrence for the differences along diagonals.

Let's set k = n-m. Then we have C_{m, m+k}. The recurrence might simplify.

Alternatively, we can use the method from the paper "The Average Number of Comparisons in Hoare's FIND" by Knuth? Actually, Knuth discusses this in the book. I think the exact formula is: C_{mn} = 2(n+1)H_n - 2(n+3-2m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? No.

Let's test the formula C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? n=3,m=2: 44/3 - 221.5=44/3-6=26/3 - 9 +8 = 26/3 -1 = 23/3? No.

Maybe the formula is: C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n+1-m} - 2(m+1)H_m + 2n + 2? n=3,m=2: H_3=11/6, H_2=3/2, H_2=3/2. 2411/6=44/3. -223/2=-6. -233/2=-9. +8. 44/3 -7 = 23/3. No.

Let's search my memory for the exact formula from the answer to exercise 32 in TAOCP Vol 3. I recall that the answer is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But we saw it's off. Wait, maybe I miscalculated C_{1n} for that formula. Let's recompute C_{1n} from that formula: C_{1n} = 2(n+1)H_n - 2(n+2-1)H_{n-1+1} - 2(1+1)H_1 + 2n + 2 = 2(n+1)H_n - 2(n+1)H_n - 4*1 + 2n + 2 = 2n - 2. But earlier we derived C_{1n} = 2n - 2H_n. So the formula gives 2n - 2, while our derived C_{1n} is 2n - 2H_n. So the difference is -2H_n + 2. That means the formula is missing a -2H_n + 2 term? Actually, if the correct formula is 2n - 2H_n, then the formula in the book might be 2n - 2H_n? But the formula I recalled has 2n - 2. So maybe the book's formula is different.

Let's check if there is a known formula for the average number of comparisons in quickselect. I can derive it from scratch using the "probability that an element is compared" method.

Let the elements be 1,2,...,n. We want element m. The algorithm picks a pivot uniformly from the current subarray containing m. The process is equivalent to: we have a random permutation of the elements. We scan the permutation from left to right; the first element that falls in the current interval containing m is chosen as pivot. This is exactly the process of building a random BST and following the path to m.

The expected number of comparisons is the expected sum over all elements x ≠ m of the number of times x is compared. x is compared each time a pivot is chosen from the current subarray containing m, and x is in that subarray. This happens for each pivot that is an ancestor of m and for which x is in the subtree containing m. In a random BST, the path from root to m consists of a sequence of nodes. For a given x, the number of comparisons involving x is the number of nodes on the path from root to m that are also ancestors of x? Actually, if x is not on the path, it will be compared exactly once: with the first node on the path to m that is an ancestor of x? Or with all ancestors of x that are on the path to m? Let's think: In quickselect, when we pick a pivot y that is on the path to m, we compare y with all other elements in the current subarray. The current subarray is exactly the set of elements in the subtree of y that contains m. So x is compared with y if and only if x is in that subtree. This means that x is compared with all ancestors of m that are also ancestors of x? Wait, if x is in the subtree of y that contains m, then the path from y to m goes through the child of y that is an ancestor of x? Not necessarily. If x is in the subtree of y that contains m, then the lowest common ancestor of x and m is some node z that is a descendant of y. So y is an ancestor of both x and m. So x is compared with y if y is an ancestor of both x and m. And since y is on the path to m, it is an ancestor of m. So x is compared with y if and only if y is an ancestor of x. Thus, x is compared with every node on the path from the root to m that is also an ancestor of x. The number of such nodes is the number of common ancestors of x and m, which is exactly the depth of the lowest common ancestor (LCA) of x and m in the random BST. In a random BST, the expected depth of the LCA of two nodes with ranks x and m can be computed.

The expected number of comparisons is sum_{x ≠ m} E[depth(LCA(x,m))]. Plus maybe something for m itself? m is compared with each pivot on the path? Actually, m is compared with each pivot chosen (since m is in the current subarray until it becomes pivot). So m is compared with each pivot on the path to m, including the final pivot when m is chosen? When m is chosen as pivot, it is compared with all other elements in the current subarray. That is the final set of comparisons. But in the process, m is compared with all its ancestors. So m is compared depth(m) times? Actually, the root is the first pivot, and m is compared with it. Then the next pivot is compared with m, etc. So m is compared with each node on the path from root to m, including itself? When m is chosen as pivot, it is compared with the remaining elements, which includes comparisons with those elements. But the comparison of m with itself doesn't happen. The number of comparisons involving m is the number of pivots chosen before m, plus the comparisons m makes when it is pivot (which is the size of its subarray minus 1). So total comparisons = sum_{x} (number of pivots that are ancestors of x and on the path to m?) This is getting complicated.

There is a simpler approach: The total number of comparisons is equal to the sum over all pivots chosen of (size of subarray - 1). The expected size of the subarray when the k-th pivot is chosen can be computed.

But maybe we can find the exact formula by looking at the recurrence and using generating functions. Let's try to solve the recurrence for C_{mn} by converting it to a difference equation.

We have: n C_{mn} = n(n-1) + sum_{j=1}^{m-1} C_{j, n-m+j} + sum_{j=m}^{n-1} C_{m, j}.

Let's consider the function F(m,n) = C_{mn} + 2H_n? No.

I recall a trick: Define U_{mn} = C_{mn} + 2? Then the recurrence might become homogeneous? Let's try to find a function that satisfies the homogeneous part.

Suppose we want to find a solution to the homogeneous recurrence: n X_{mn} = sum_{j=1}^{m-1} X_{j, n-m+j} + sum_{j=m}^{n-1} X_{m, j}.

If we can find a particular solution for the nonhomogeneous part n(n-1), and add the homogeneous solution.

The nonhomogeneous part is n(n-1). We can try a particular solution of the form a n + b n^2? But the recurrence involves C_{j, n-m+j} which depends on the difference n-m. Maybe we can use the fact that the sum of C over m yields something.

Let's sum the recurrence over m from 1 to n: sum_{m=1}^n n C_{mn} = n^2(n-1) + sum_{m=1}^n sum_{j=1}^{m-1} C_{j, n-m+j} + sum_{m=1}^n sum_{j=m}^{n-1} C_{m, j}.

The double sums can be rearranged. The first double sum: sum_{m=1}^n sum_{j=1}^{m-1} C_{j, n-m+j}. Let k = m-j. Then m = j+k, k=1..n-j. The sum becomes sum_{j=1}^{n-1} sum_{k=1}^{n-j} C_{j, n-j}? Wait, n-m+j = n - (j+k) + j = n - k. So it's sum_{j=1}^{n-1} sum_{k=1}^{n-j} C_{j, n-k}. The second double sum: sum_{m=1}^n sum_{j=m}^{n-1} C_{m, j} = sum_{j=1}^{n-1} sum_{m=1}^{j} C_{m, j} = sum_{j=1}^{n-1} sum_{m=1}^{j} C_{m, j}. This is symmetric to the first? Not exactly.

But maybe we don't need to sum over m. The problem asks for C_{mn} and then the asymptotic for C_{(2m-1)m} (median of 2m-1). So we need the exact formula and then the asymptotic.

I am fairly confident that the exact formula for the average number of comparisons in Hoare's FIND (quickselect) is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But we saw it doesn't match our computed small values. Let me re-check the small values computation. Maybe I made a mistake in the recurrence or in the base case.

Let's read the problem statement carefully: "Find a simple closed form expression for C_{mn}, the average number of key comparisons required to select the mth smallest of n elements by the 'quickfind' method of exercise 31. (For simplicity, let M = 1; that is, don't assume the use of a special technique for short subfiles.)"

What is M? In quicksort, sometimes M is the cutoff for using insertion sort on small subfiles. If M=1, we don't use insertion sort, so we just use the quickfind algorithm all the way down to subfiles of size 1. The partitioning step in quicksort (Algorithm Q) in Knuth's book might have a specific number of comparisons. I should we need to be careful.

In the text provided, they analyze bubble sort. There is no analysis of quicksort in the provided text. The exercises 29,30,31 are separate. Exercise 31 says: "Show that quicksort can be adapted to this purpose, avoiding many of the computations required to do a complete sort." This is Hoare's FIND algorithm. The algorithm is: pick a pivot, partition the array into elements < pivot and > pivot. If the pivot is the m-th, stop. Else if m is less than pivot index, recurse on left; else recurse on right with adjusted m.

The number of key comparisons in partitioning n elements: In Hoare's partition algorithm, you compare the pivot with other elements. In the standard implementation, you have two indices i and j, and you do comparisons like A[i] < pivot and A[j] > pivot. The total number of key comparisons is n+1 in the worst case? Actually, in the analysis of quicksort in Knuth's book (Section 5.2.2), the average number of comparisons is given as 2n ln n + O(n). The exact formula might be in the exercises or in the text of a later section. I recall that in TAOCP Vol 3, Section 5.2.3 "Minimum-Comparison Selection", the average number of comparisons for quickselect is given as: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? I'm going to check this against known literature.

I can search my memory for the exact formula from "The Art of Computer Programming, Volume 3, Exercise 5.2.2-32". The answer is likely in the back of the book. I remember that the formula for the average number of comparisons in quickselect is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2. But we saw it gives 2 for n=2,m=1, while we thought it should be 1. Maybe the partitioning cost is n? If partitioning cost is n, then C_{12}=2. Let's check the recurrence with cost n: C_{1n} = n + (1/n) sum_{j=1}^{n-1} C_{1j}. Then C_{12}=2, C_{13}=3+2/3=11/3, etc. The formula 2n-2 gives C_{12}=2, C_{13}=4, not 11/3. So that formula doesn't match cost n either.

What if the formula is C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n? For m=1: 2n - 2. Still not 2n - 2H_n.

Wait, maybe the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2H_n? That would be 2n H_n? No.

Let's look at the structure: The recurrence is linear and can be solved by noticing that C_{mn} satisfies: C_{mn} = 2n - 2H_n + something? Actually, we can try to find the solution by the method of "induction on n".

Assume the formula is of the form: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2 \delta_{something}? No.

I found a paper in my memory: "The average number of comparisons in Hoare's FIND" by Knuth? Actually, the exact formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But that is for the number of comparisons in a variant where the pivot is compared with all elements including itself? Or maybe the formula is for the number of comparisons including the final check?

Let's test the formula with our computed values for n=3,m=2. The formula gave 14/3 ≈ 4.667. Our computed C23 was 8/3 ≈ 2.667. The difference is 2. For n=4,m=2, formula 43/6 ≈ 7.167, computed 9/2=4.5, difference 16/6=8/3≈2.667. For n=5,m=3, formula 151/15≈10.067, computed 101/15≈6.733, difference 50/15=10/3≈3.333. The difference seems to be 2H_n? For n=3, 2H_3=11/3≈3.667, not 2. For n=4, 2H_4=25/6≈4.167, not 8/3. For n=5, 2H_5=274/60≈4.567, not 10/3.

Maybe the formula is C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2? That would be 2n? No.

Let's try to derive the exact formula by solving the recurrence with a known method.

We have: n C_{mn} = n(n-1) + sum_{j=1}^{m-1} C_{j, n-m+j} + sum_{j=m}^{n-1} C_{m, j}. (1)

Let's define for fixed d = n-m, and let m vary. But maybe we can use the substitution: Let D_{mn} = C_{mn} + 2? Not sure.

Consider the recurrence for the difference: Let E_{mn} = C_{mn} - C_{m-1,n} for m>1. We already tried that.

Another approach: Use generating functions or the "recurrence for expectations" by considering the probability that a given element is compared. I think the probability that element x is compared with element y in quickselect is:

If x < m < y or y < m < x (i.e., m is between x and y), then probability = 2/(y-x+1).
If both x and y are on the same side of m, then probability = 2/(y-x+1) * something? Actually, I recall that in quickselect, the probability that two elements are compared is 2/(|x-y|+1) if the subarray containing m also contains both? Wait, we saw for n=3,m=1, x=2,y=3 (both > m), probability was 2/3. And 2/(3-2+1)=1. So it's not 2/(y-x+1). It's something else.

Let's compute the probability that x and y are compared for general m. The algorithm only processes intervals containing m. The first pivot chosen from the set of elements that are in the current interval and also in [min(x,y), max(x,y)] will be compared with the other if it is either x or y. But the current interval always contains m. So the set of candidates for the first pivot from [x,y] is the intersection of the random permutation with [x,y]? The process is equivalent to: we have a random permutation of all elements. We look at the elements in the order of the permutation. The first element that falls in the current interval containing m is chosen as pivot. The current interval shrinks. The elements x and y are compared if and only if the first element from [x,y] that appears in the permutation is either x or y, AND m is not between x and y? Or something.

Actually, there's a known result: In quickselect, the probability that two elements with ranks i and j are compared is: P(i,j) = 2/(j-i+1) if i <= m <= j, P(i,j) = 2/(j-i+1) * (something) if both < m or both > m. Let's derive it properly.

Consider the random BST model. In a random BST, the path from root to m is a random sequence of nodes. The comparisons are all pairs (u, v) where u is on the path to m, and v is in the subtree of u that contains m. This is equivalent to: for each node x ≠ m, the number of comparisons involving x is the number of ancestors of m that are also ancestors of x. This is exactly the number of nodes on the path from the root to the LCA of x and m. In a random BST, the expected number of common ancestors of x and m (including the LCA?) is something like H_{|x-m|+1} + H_{...}? I'm not sure.

Let's look for the exact formula in the literature. I recall that the expected number of comparisons in Hoare's FIND is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? I've seen this formula in a paper by Knuth or in the book "The Art of Computer Programming" Volume 3, Exercise 5.2.2-32. The answer in the book might be exactly that. But why did my small-n calculations not match? Let's re-examine the base case and the recurrence.

Maybe the recurrence for C_{mn} in the book is different. The exercise says "For simplicity, let M = 1; that is, don't assume the use of a special technique for short subfiles." This suggests that the algorithm has a parameter M for the cutoff. In quicksort, when the subfile size is <= M, you use a different method (like insertion sort). For M=1, you use the same method for all sizes, but maybe the method for size 1 does nothing, so C_{11}=0. But maybe the partitioning step for size n does n comparisons? Let's check the standard quicksort partitioning in Knuth's Algorithm Q. In the MIX program for Algorithm Q, the partitioning inner loop does comparisons. I think the number of comparisons is n+1? Let's check the text: In Section 5.2.2, they give Program Q for quicksort. The analysis of quicksort is in Section 5.2.2? Actually, the provided text only shows bubble sort. But the exercises refer to quicksort. In the summary at the end of Section 5.2 (maybe later), Knuth gives formulas for various sorts. I know that the average number of comparisons for quicksort is 2n ln n + O(n). The exact formula is often given as 2(n+1)H_n - 4n? Let's check: For n=3, 2411/6 - 12 = 88/6 - 12 = 14.666 - 12 = 2.666? That's too low for quicksort. Quicksort on 3 elements average comparisons is 8/3 ≈ 2.666. For n=4, quicksort average is? 2525/12 - 16 = 250/12 - 16 = 20.833 - 16 = 4.833. But quicksort on 4 elements: average comparisons is 29/6 ≈ 4.833? Actually, quicksort on 4: I think it's 29/6 = 4.833. Yes, 2(n+1)H_n - 4n gives 29/6 for n=4. So quicksort average comparisons = 2(n+1)H_n - 4n. This matches the recurrence C_n = n+1 + (2/n) sum_{k=1}^{n-1} C_k? Let's test: C_1=0. C_2 = 3 + 0 = 3? But 231.5 - 8 = 9-8=1. So that recurrence gives 3, not 1. So the recurrence for quicksort with cost n+1 gives C_2=3, but the formula 2(n+1)H_n - 4n gives 1 for n=2. Contradiction. Let's recompute quicksort average comparisons exactly.

Quicksort: choose pivot uniformly, partition (cost?), then recurse on left and right. The total comparisons = partition cost + C_left + C_right. If partition cost is n-1, then C_n = n-1 + (1/n) sum_{k=1}^n (C_{k-1} + C_{n-k}) = n-1 + (2/n) sum_{k=1}^{n-1} C_k. For n=2: C_2 = 1 + (2/2)C_1 = 1. For n=3: C_3 = 2 + (2/3)(C_1+C_2) = 2 + (2/3)1 = 8/3 ≈ 2.666. For n=4: C_4 = 3 + (2/4)(C_1+C_2+C_3) = 3 + (1/2)(0+1+8/3) = 3 + (1/2)(11/3) = 3 + 11/6 = 29/6 ≈ 4.833. The formula 2(n+1)H_n - 4n for n=2: 231.5 - 8 = 9-8=1. For n=3: 2411/6 - 12 = 88/6 - 12 = 14.666 - 12 = 2.666. For n=4: 2525/12 - 16 = 250/12 - 16 = 20.833 - 16 = 4.833. So the formula matches the recurrence with partition cost n-1! Because 2(n+1)H_n - 4n solves C_n = n-1 + (2/n) sum C_k. Let's verify: If C_n = 2(n+1)H_n - 4n, then for n=2, C_2 = 231.5 - 8 = 1. Good. So the recurrence with partition cost n-1 yields the formula 2(n+1)H_n - 4n. But earlier I thought the standard quicksort formula was 2(n+1)H_n - 4n. Yes, that's correct. So quicksort partition cost is n-1.

Now, for quickselect, the partition cost is also n-1 (comparing pivot with n-1 other elements). So our recurrence is correct.

Now, why does the formula I recalled (2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2) not match? Let's check if that formula satisfies the quickselect recurrence with partition cost n-1.

Let's test the formula F(m,n) = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 for n=2,m=1: F=2. The recurrence would require F(1,2) = 1 + (1/2)*0 = 1. So F doesn't satisfy the recurrence.

Maybe the correct formula is F(m,n) = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n? For n=2,m=1: 231.5 - 231.5 - 4 + 4 = 0. Not 1.

Maybe the formula is F(m,n) = 2(n+1)H_n - 2(n+1-m)H_{n-m+1} - 2(m+1)H_m + 2n? n=2,m=1: 9 - 221.5 - 4 + 4 = 9 - 6 = 3.

None match.

Let's derive the exact formula by solving the recurrence. We have: n C_{mn} = n(n-1) + sum_{j=1}^{m-1} C_{j, n-m+j} + sum_{j=m}^{n-1} C_{m, j}.

We can try to find a pattern by computing C_{mn} for all m,n up to 5 and see if we can guess a formula.

We have: n=1: C11=0 n=2: C12=1, C22=1 n=3: C13=7/3, C23=8/3, C33=7/3 n=4: C14=23/6, C24=9/2, C34=9/2, C44=23/6 n=5: C15=163/30, C25=32/5, C35=101/15, C45=32/5, C55=163/30 n=6: C16=71/10, C26=25/3, C36=?, C46=?, C56=?, C66=? Let's compute C36 for n=6,m=3. C_{36} = 5 + (1/6)[ sum_{k=1}^{2} C_{3-k, 6-k} + sum_{k=4}^{6} C_{3, k-1} ]. k=1: C_{2,5} = 32/5 = 6.4 k=2: C_{1,4} = 23/6 ≈ 3.833 Sum left = 32/5 + 23/6 = 192/30 + 115/30 = 307/30 ≈ 10.233. k=4: C_{3,3} = 7/3 ≈ 2.333 k=5: C_{3,4} = 9/2 = 4.5 k=6: C_{3,5} = 101/15 ≈ 6.733 Sum right = 7/3 + 9/2 + 101/15 = 70/30 + 135/30 + 202/30 = 407/30 ≈ 13.567. Total sum = 714/30 = 119/5 = 23.8. C36 = 5 + (119/5)/6 = 5 + 119/30 = 150/30 + 119/30 = 269/30 ≈ 8.9667. C46 symmetric to C36? n=6,m=4 is symmetric to m=3? Actually symmetry is C_{mn} = C_{n+1-m,n}. For n=6, C46 = C_{36} = 269/30. C26 = 25/3 = 250/30 ≈ 8.333. C56 = C26 = 25/3. C16 = 71/10 = 213/30 = 7.1. C66 = 71/10.

Now we have a table: n=1: 0 n=2: 1, 1 n=3: 2.333, 2.667, 2.333 n=4: 3.833, 4.5, 4.5, 3.833 n=5: 5.433, 6.4, 6.733, 6.4, 5.433 n=6: 7.1, 8.333, 8.967, 8.967, 8.333, 7.1

Let's compute differences from 2n: 2n - C_{mn}: n=2: 4-1=3, 4-1=3 n=3: 6-2.333=3.667, 6-2.667=3.333, 3.667 n=4: 8-3.833=4.167, 8-4.5=3.5, 3.5, 4.167 n=5: 10-5.433=4.567, 10-6.4=3.6, 10-6.733=3.267, 3.6, 4.567 n=6: 12-7.1=4.9, 12-8.333=3.667, 12-8.967=3.033, 3.033, 3.667, 4.9

Notice that for m=1 (and m=n), 2n - C_{1n} = 2H_n. For n=3: 2H_3=211/6=3.667. n=4: 225/12=4.167. n=5: 2137/60=4.567. n=6: 249/20=4.9. Matches! For m=2 (and m=n-1), 2n - C_{2n} = ? n=3: 3.333 = 10/3? 2H_3 - 2/3? 11/3 - 2/3 = 9/3=3? Not 10/3. n=4: 3.5 = 7/2. 2H_4 = 25/6 ≈ 4.167. Difference 0.667 = 2/3. n=5: 3.6 = 18/5. 2H_5 = 137/30 ≈ 4.567. Difference 0.967 = 29/30. n=6: 3.667 = 11/3. 2H_6 = 49/10 = 4.9. Difference 1.233 = 37/30. These differences are exactly the d_n we computed earlier.

For m=3 (and m=n-2): n=5: 3.267 = 49/15? 10 - 101/15 = 49/15 ≈ 3.267. 2H_5 = 137/30 = 4.567. Difference = 137/30 - 49/15 = 137/30 - 98/30 = 39/30 = 13/10 = 1.3. n=6: 3.033 = 91/30? 12 - 269/30 = 91/30 ≈ 3.033. 2H_6 = 49/10 = 147/30. Difference = 147/30 - 91/30 = 56/30 = 28/15 ≈ 1.867.

The differences seem to be related to harmonic numbers of smaller indices. Maybe the formula is: C_{mn} = 2(n+1)H_n - 2(n+1-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? No.

Let's try to find the formula by looking at the recurrence for the differences.

Define D_{mn} = C_{mn} - C_{m-1,n} for m>=2. We have symmetry, so we can focus on m <= n/2. For n=3: D_{23} = C23 - C13 = 1/3. For n=4: D_{24} = 9/2 - 23/6 = 4/6 = 2/3. D_{34} = 0. For n=5: D_{25} = 32/5 - 163/30 = 192/30 - 163/30 = 29/30. D_{35} = 101/15 - 32/5 = 101/15 - 96/15 = 5/15 = 1/3. For n=6: D_{26} = 25/3 - 71/10 = 250/30 - 213/30 = 37/30. D_{36} = 269/30 - 25/3 = 269/30 - 250/30 = 19/30. D_{46} = 0 (by symmetry? Actually m=4, n=6, m > n/2, but symmetry says C_{46}=C_{36}, so D_{46} = C_{46} - C_{36} = 0).

So D_{mn} for m <= floor(n/2) seems positive and decreasing? Not necessarily.

Maybe the formula for C_{mn} is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2H_m - 2H_{n-m+1}? No.

Let's look at the expression 2(n+1)H_n - 2(n+1-m)H_{n-m+1} - 2(m+1)H_m + 2n. For n=3,m=2: 44/3 - 6 - 9 + 6 = 44/3 -9 = 17/3 ≈ 5.667. Not 8/3.

What about 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n? n=3,m=2: 44/3 - 9 - 9 + 6 = 44/3 -12 = 8/3. That matches! n=3,m=1: 44/3 - 24H_3? n+2-m = 4, H_{n-m+1}=H_3. -2411/6 = -88/6 = -44/3. -221 = -4. +6. Total = 44/3 -44/3 -4 +6 = 2. But C13=7/3. So for m=1 it gives 2, not 7/3. So the formula 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n works for m=2,n=3 but not for m=1.

Maybe the formula is piecewise? Or maybe the recurrence for m=1 is different because the sum from j=1 to m-1 is empty? But the recurrence we used is the same.

Let's check the recurrence for m=1 with the formula F(m,n) = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n. For m=1: F(1,n) = 2(n+1)H_n - 2(n+1)H_n - 4 + 2n = 2n - 4. But we know C_{1n} = 2n - 2H_n. So F is off by -2H_n + 4. For m=2: F(2,n) = 2(n+1)H_n - 2(n)H_{n-1} - 6H_2 + 2n. We know C_{2n} from our computed values. Let's compute F(2,n) for n=3: 44/3 - 6H_2? n=3: 2411/6=44/3. -23H_2 = -61.5=-9. -61.5=-9. +6=6. Sum=44/3 -12 = 8/3. Matches C23=8/3. For n=4: F(2,4) = 2525/12 - 24H_3 - 9 + 8 = 125/6 - 811/6 - 1 = 125/6 - 88/6 - 1 = 37/6 - 1 = 31/6 ≈ 5.167. But C24=9/2=27/6=4.5. So F(2,4) = 31/6, C24=27/6. Difference = 4/6=2/3. So F works for n=3,m=2 but not for n=4,m=2.

Maybe the formula is F(m,n) = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2H_n? For m=2,n=4: 125/6 - 811/6? n+2-m=4, H_3=11/6. -2411/6 = -88/6. -23*1.5=-9. +8+2=10. -2H_4 = -50/12 = -25/6. Sum = 125/6 - 88/6 - 9 + 10 - 25/6 = (125-88-25)/6 +1 = 12/6+1=2+1=3. Not 4.5.

This is getting messy. Let's try to find the exact formula by solving the recurrence with a known technique.

We have the recurrence: n C_{mn} = n(n-1) + \sum_{j=1}^{m-1} C_{j, n-m+j} + \sum_{j=m}^{n-1} C_{m, j}.

Let's define for each n, a sequence C_{m,n} for m=1..n. We can write this as: C_{m,n} = n-1 + \frac{1}{n} \left( \sum_{j=1}^{m-1} C_{j, n-m+j} + \sum_{j=m}^{n-1} C_{m, j} \right).

Consider the generating function? Alternatively, we can use the method from Knuth's book "The Art of Computer Programming" Volume 3, where he solves this exact recurrence in the answer to Exercise 32. I recall the answer is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But we saw it doesn't match. Maybe the book uses a different definition of H_n? H_n = 1 + 1/2 + ... + 1/n. That's standard.

Wait, maybe the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2H_n - 2? No.

Let's search my memory for the exact formula from the solution to Exercise 5.2.2-32. I think the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? And the asymptotic for the median is C_{(2m-1)m} ~ 2m(2H_{2m} - H_m - H_{m+1} + 1)? Or something like that.

Wait, I found a note in my memory: The average number of comparisons in Hoare's FIND is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? And the values for small n are: n=1: 0 n=2: C12=2? But that would mean the book's C12 is 2, not 1. Why would it be 2? Because the partitioning algorithm in Knuth's quicksort (Algorithm Q) might use a different number of comparisons. In Algorithm Q, the partitioning step might compare the pivot with all n elements? Let's check the MIX program for Algorithm Q in the book. I don't have it in the provided text, but I know that in Knuth's quicksort, the number of comparisons is n+1 for partitioning? Actually, in the analysis of quicksort in Section 5.2.2, the average number of comparisons is given as 2n ln n + O(n). The exact formula for quicksort comparisons is 2(n+1)H_n - 4n? That gave 1 for n=2. But if the quicksort partition cost is n+1, the formula would be different.

Let's check the formula 2(n+1)H_n - 4n for n=2: 231.5 - 8 = 1. So quicksort average comparisons is 1 for n=2? But quicksort on 2 elements: you compare the two elements once, then you're done. That's 1 comparison. So partition cost is 1 = n-1. So quicksort uses n-1 comparisons for partition.

Then quickselect should also use n-1. So C12=1.

But the formula I recalled gives 2 for n=2. So maybe the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n? That gives 0 for n=2,m=1. What about: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2? That's 2n.

Maybe the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2H_n - 2? No.

Let's try to find the correct formula by matching the values we have with a general expression.

We have C_{1n} = 2n - 2H_n. We have C_{2n} = ? Let's find an expression for C_{2n} in terms of H_n. From the recurrence for m=2: n C_{2n} = n(n-1) + C_{1, n-1} + \sum_{j=2}^{n-1} C_{2j}. We know C_{1, n-1} = 2(n-1) - 2H_{n-1}. Let S_n = \sum_{j=2}^{n} C_{2j}. Then C_{2n} = S_n - S_{n-1}. n(S_n - S_{n-1}) = n(n-1) + 2n - 2 - 2H_{n-1} + S_{n-1}. n S_n = (n+1) S_{n-1} + n^2 + n - 2 - 2H_{n-1}. Divide by n(n+1): S_n/(n+1) = S_{n-1}/n + (n^2+n-2)/(n(n+1)) - 2H_{n-1}/(n(n+1)). (n^2+n-2) = (n+2)(n-1). So (n+2)(n-1)/(n(n+1)) = (n+2)/n * (n-1)/(n+1). Not a simple harmonic.

Maybe we can compute S_n/(n+1) explicitly. S_2 = C_{22} = 1. S_2/3 = 1/3. S_3 = 1 + 8/3 = 11/3. S_3/4 = 11/12. S_4 = 11/3 + 9/2 = 22/6 + 27/6 = 49/6. S_4/5 = 49/30. S_5 = 49/6 + 32/5 = 245/30 + 192/30 = 437/30. S_5/6 = 437/180 ≈ 2.4278. S_6 = 437/30 + 25/3 = 437/30 + 250/30 = 687/30 = 229/10. S_6/7 = 229/70 ≈ 3.2714.

Now, can we express S_n/(n+1) in terms of harmonic numbers? For n=2: 1/3. n=3: 11/12 = 0.9167. n=4: 49/30 ≈ 1.633. n=5: 437/180 ≈ 2.4278. n=6: 229/70 ≈ 3.2714.

Maybe S_n/(n+1) = 2H_n - something? 2H_2 = 3, 1/3 is not 3. 2H_3 = 11/3 ≈ 3.667, 11/12 is 0.9167. So not.

Maybe C_{mn} can be expressed as: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2 \sum_{i=1}^{m} \frac{1}{i} - 2 \sum_{i=1}^{n-m+1} \frac{1}{i}? No.

Let's think about the continuous limit. The expected number of comparisons for quickselect to find the m-th smallest out of n is approximately n * f(m/n) where f(p) is the solution to an integral equation. For median p=1/2, f(1/2) = 2(1 + ln 2) ≈ 3.386. Our computed values for median: n=3,m=2: C23=2.667, n=3, 2.667/3=0.889? Not 3.386. Wait, n=3 is small. For n=5,m=3: C35=101/15≈6.733, 6.733/5=1.347. For n=7? Not computed. The asymptotic constant is for large n. Our small n values are not close to 3.386n. For n=3, 3.386*3=10.16, but C23=2.667. So the formula 2(n+1)H_n - ... with leading term 2n ln n? Actually, for fixed m, C_{mn} ~ 2n. For m ~ n/2, C_{mn} ~ 2(1+ln 2)n ≈ 3.386n. So the leading term is linear in n, not n log n. Our C_{1n} = 2n - 2H_n ~ 2n - 2 log n. So linear. The formula 2(n+1)H_n ~ 2n log n would be too large. So the correct formula must be linear in n, not n log n. The formula I recalled had 2(n+1)H_n which is ~ 2n log n. That would be for quicksort, not quickselect! Quickselect average comparisons is linear in n, not n log n. Yes! Quickselect is O(n) average comparisons. The formula 2(n+1)H_n is O(n log n). So the formula I recalled is for quicksort, not quickselect! That's the mistake.

Quickselect average comparisons is indeed linear. The recurrence C_{mn} = n-1 + ... yields C_{mn} ~ c n. The formula should involve harmonic numbers but not multiplied by n? Wait, our C_{1n} = 2n - 2H_n. That's 2n minus log n. The coefficient of n is 2. For median, the coefficient is about 3.386. So the formula should be of the form C_{mn} = n * g(m/n) + lower order terms.

But the problem asks for a "simple closed form expression". It might be expressed in terms of harmonic numbers, like C_{mn} = 2n - 2H_n + something? But for general m, it might be a sum of harmonic numbers.

Let's look at the values: C_{1n} = 2n - 2H_n. C_{2n} = ? We can try to express C_{2n} as 2n - 2H_n + 2H_{n-1}? For n=3: 23 - 211/6 + 21.5 = 6 - 11/3 + 3 = 9 - 11/3 = 16/3 ≈ 5.333, not 8/3. Maybe C_{mn} = 2n - 2H_m - 2H_{n-m+1} + 2H_n? Let's test: For n=3,m=1: 6 - 21 - 2H_3 + 2H_3 = 6 - 2 = 4. Not 7/3. For n=3,m=2: 6 - 2H_2 - 2H_2 + 2*H_3 = 6 - 3 - 3 + 11/3 = 11/3 ≈ 3.667. Not 8/3.

Maybe C_{mn} = 2n - 2H_n + 2 \sum_{i=1}^{m-1} \frac{1}{i} + 2 \sum_{i=1}^{n-m} \frac{1}{i}? That's 2n - 2H_n + 2H_{m-1} + 2H_{n-m}. For n=3,m=2: 6 - 11/3 + 21 + 21 = 6 - 11/3 + 4 = 10 - 11/3 = 19/3 ≈ 6.333. No.

Let's try to find the pattern by looking at C_{mn} + C_{m-1,n} or something.

I recall that the exact formula for the average number of comparisons in Hoare's FIND is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But that's O(n log n). That is the formula for the number of comparisons in a variant where you sort the whole array? No, quicksort is O(n log n). Quickselect is O(n). So the formula cannot have n H_n. The recurrence we have yields linear in n because the nonhomogeneous term is n(n-1), and the sum of C's is over O(n) terms? Actually, the recurrence is n C_{mn} = n(n-1) + sum of C's. If C_{mn} is O(n), then left side is O(n^2), right side sum of O(n) terms each O(n) is O(n^2), consistent. So C_{mn} is O(n). So the closed form should be a linear combination of n and harmonic numbers without n multiplying harmonic numbers.

Our C_{1n} = 2n - 2H_n. That's linear in n plus harmonic. C_{2n} seems to be 2n - 2H_n + something like 2/n? For n=3: 23 - 211/6 = 7/3, but C23=8/3. So C23 = C13 + 1/3. For n=4: C14=23/6, C24=27/6. Difference = 4/6=2/3. For n=5: C15=163/30, C25=192/30. Diff=29/30. For n=6: C16=213/30, C26=250/30. Diff=37/30. So C_{2n} = C_{1n} + d_n, where d_n = ? d_2=0, d_3=1/3, d_4=2/3, d_5=29/30, d_6=37/30. d_n = ? Maybe d_n = 2 \sum_{i=2}^{n} \frac{1}{i} - 2? For n=3: 2*(1/2+1/3) - 2 = 2*(5/6) - 2 = 5/3 - 2 = -1/3. No. Maybe d_n = 2 \sum_{i=1}^{n-1} \frac{1}{i+1} - 2? Not.

Let's compute d_n in terms of harmonic numbers: d_2=0 d_3=1/3 d_4=2/3 = 20/30 d_5=29/30 d_6=37/30 H_n: H_2=1.5, H_3=1.833, H_4=2.083, H_5=2.283, H_6=2.45. Not obvious.

Maybe the formula for C_{mn} is: C_{mn} = 2n - 2H_n + 2 \sum_{i=1}^{m-1} \frac{1}{i} \frac{n-m+i}{n}? No.

Let's try to solve the recurrence using the "difference" method with respect to n.

Define D_{m,n} = C_{m,n} - C_{m,n-1} for n > m. From the recurrence: n C_{m,n} = n(n-1) + \sum_{j=1}^{m-1} C_{j, n-m+j} + \sum_{j=m}^{n-1} C_{m, j}. (n-1) C_{m,n-1} = (n-1)(n-2) + \sum_{j=1}^{m-1} C_{j, n-1-m+j} + \sum_{j=m}^{n-2} C_{m, j}. Subtract: n C_{m,n} - (n-1) C_{m,n-1} = 2n-2 + \sum_{j=1}^{m-1} [C_{j, n-m+j} - C_{j, n-m-1+j}] + C_{m, n-1}. So n D_{m,n} + C_{m,n-1} = 2n-2 + \sum_{j=1}^{m-1} D_{j, n-m+j} + C_{m, n-1}. Thus n D_{m,n} = 2n-2 + \sum_{j=1}^{m-1} D_{j, n-m+j}. So D_{m,n} = 2 - 2/n + (1/n) \sum_{j=1}^{m-1} D_{j, n-m+j}. (2)

This is a recurrence for D. For m=1, the sum is empty, so D_{1,n} = 2 - 2/n. Then C_{1,n} = C_{1,1} + \sum_{k=2}^{n} D_{1,k} = 0 + \sum_{k=2}^{n} (2 - 2/k) = 2(n-1) - 2(H_n - 1) = 2n - 2 - 2H_n + 2 = 2n - 2H_n. Matches!

Now for m=2: D_{2,n} = 2 - 2/n + (1/n) D_{1, n-2+1} = 2 - 2/n + (1/n) D_{1, n-1}. D_{1, n-1} = 2 - 2/(n-1) for n-1 >= 2 => n >= 3. So for n>=3: D_{2,n} = 2 - 2/n + (1/n)(2 - 2/(n-1)) = 2 - 2/n + 2/n - 2/(n(n-1)) = 2 - 2/(n(n-1)). Check for n=3: D_{2,3} = 2 - 2/(32) = 2 - 1/3 = 5/3. C_{2,3} = C_{2,2} + D_{2,3} = 1 + 5/3 = 8/3. Matches! For n=4: D_{2,4} = 2 - 2/(43) = 2 - 1/6 = 11/6. C_{2,4} = C_{2,3} + D_{2,4} = 8/3 + 11/6 = 16/6 + 11/6 = 27/6 = 9/2. Matches! For n=5: D_{2,5} = 2 - 2/(54) = 2 - 1/10 = 19/10. C_{2,5} = 9/2 + 19/10 = 45/10 + 19/10 = 64/10 = 32/5. Matches! For n=6: D_{2,6} = 2 - 2/(65) = 2 - 1/15 = 29/15. C_{2,6} = 32/5 + 29/15 = 96/15 + 29/15 = 125/15 = 25/3. Matches!

Great! So we have a simple recurrence for D_{m,n}: D_{m,n} = 2 - 2/n + (1/n) \sum_{j=1}^{m-1} D_{j, n-m+j}.

And we have D_{1,n} = 2 - 2/n.

Now we can find D_{3,n}: D_{3,n} = 2 - 2/n + (1/n)[ D_{1, n-3+1} + D_{2, n-3+2} ] = 2 - 2/n + (1/n)[ D_{1, n-2} + D_{2, n-1} ]. For n>=4. D_{1, n-2} = 2 - 2/(n-2). D_{2, n-1} = 2 - 2/((n-1)(n-2)). So D_{3,n} = 2 - 2/n + (1/n)[ 4 - 2/(n-2) - 2/((n-1)(n-2)) ]. Let's test for n=4: D_{3,4} = 2 - 2/4 + (1/4)[ D_{1,2} + D_{2,3} ]. D_{1,2} = 2 - 2/2 = 1. D_{2,3} = 5/3. Sum = 1 + 5/3 = 8/3. D_{3,4} = 2 - 0.5 + (8/3)/4 = 1.5 + 2/3 = 1.5 + 0.6667 = 2.1667 = 13/6. C_{3,4} = C_{3,3} + D_{3,4} = 7/3 + 13/6 = 14/6 + 13/6 = 27/6 = 9/2. Matches! For n=5: D_{3,5} = 2 - 2/5 + (1/5)[ D_{1,3} + D_{2,4} ]. D_{1,3} = 2 - 2/3 = 4/3. D_{2,4} = 11/6. Sum = 4/3 + 11/6 = 8/6 + 11/6 = 19/6. D_{3,5} = 2 - 0.4 + (19/6)/5 = 1.6 + 19/30 = 48/30 + 19/30 = 67/30 ≈ 2.2333. C_{3,5} = C_{3,4} + D_{3,5} = 9/2 + 67/30 = 135/30 + 67/30 = 202/30 = 101/15. Matches! For n=6: D_{3,6} = 2 - 2/6 + (1/6)[ D_{1,4} + D_{2,5} ]. D_{1,4} = 2 - 2/4 = 1.5 = 3/2. D_{2,5} = 19/10. Sum = 3/2 + 19/10 = 15/10 + 19/10 = 34/10 = 17/5. D_{3,6} = 2 - 1/3 + (17/5)/6 = 5/3 + 17/30 = 50/30 + 17/30 = 67/30 ≈ 2.2333. C_{3,6} = C_{3,5} + D_{3,6} = 101/15 + 67/30 = 202/30 + 67/30 = 269/30. Matches!

So the recurrence for D works perfectly.

Now we can find a general expression for D_{m,n}. The recurrence is: D_{m,n} = 2 - 2/n + (1/n) \sum_{j=1}^{m-1} D_{j, n-m+j}. with D_{1,n} = 2 - 2/n.

We can try to find a pattern for D_{m,n}. For m=1: D_{1,n} = 2 - 2/n. For m=2: D_{2,n} = 2 - 2/(n(n-1)). For m=3: D_{3,n} = 2 - 2/n + (1/n)[ 2 - 2/(n-2) + 2 - 2/((n-1)(n-2)) ]? Let's compute the sum: Sum = D_{1, n-2} + D_{2, n-1} = (2 - 2/(n-2)) + (2 - 2/((n-1)(n-2))) = 4 - 2/(n-2) - 2/((n-1)(n-2)). Then D_{3,n} = 2 - 2/n + (1/n)[4 - 2/(n-2) - 2/((n-1)(n-2))] = 2 - 2/n + 4/n - 2/(n(n-2)) - 2/(n(n-1)(n-2)). = 2 + 2/n - 2/(n(n-2)) - 2/(n(n-1)(n-2)). Let's check for n=4: 2 + 2/4 - 2/(42) - 2/(432) = 2 + 0.5 - 0.25 - 2/24 = 2.25 - 0.08333 = 2.16667 = 13/6. Yes! For n=5: 2 + 2/5 - 2/(53) - 2/(543) = 2 + 0.4 - 2/15 - 2/60 = 2.4 - 0.13333 - 0.03333 = 2.23333 = 67/30. Yes!

So D_{3,n} = 2 + 2/n - 2/(n(n-2)) - 2/(n(n-1)(n-2)). For m=4: D_{4,n} = 2 - 2/n + (1/n)[ D_{1,n-3} + D_{2,n-2} + D_{3,n-1} ]. We can guess that D_{m,n} = 2 \sum_{i=0}^{m-1} (-1)^i something? Actually, the pattern suggests: D_{m,n} = 2 \sum_{k=0}^{m-1} \frac{(-1)^k}{n(n-1)...(n-k)}? Not exactly.

Let's look at the expressions: D_{1,n} = 2 - 2/n = 2(1 - 1/n). D_{2,n} = 2 - 2/(n(n-1)) = 2(1 - 1/(n(n-1))). D_{3,n} = 2 + 2/n - 2/(n(n-2)) - 2/(n(n-1)(n-2))? That's not a single product.

Wait, D_{3,n} = 2 + 2/n - 2/(n(n-2)) - 2/(n(n-1)(n-2)). Combine terms: = 2 + 2/n * [1 - 1/(n-2) * (1 + 1/(n-1))]? Not simpler.

Maybe there's a better way: The recurrence for D can be solved by noting that D_{m,n} = 2 - 2/(n(n-1)...(n-m+1))? For m=1: 2 - 2/n. m=2: 2 - 2/(n(n-1)). m=3: if pattern continued, D_{3,n} = 2 - 2/(n(n-1)(n-2)). But our computed D_{3,4} = 13/6 ≈ 2.1667, while 2 - 2/(432) = 2 - 2/24 = 2 - 1/12 = 23/12 ≈ 1.9167. Not equal. So pattern breaks.

Let's compute D_{3,n} from the expression we derived: D_{3,n} = 2 + 2/n - 2/(n(n-2)) - 2/(n(n-1)(n-2)). = 2 + (2/n)[1 - 1/(n-2) - 1/((n-1)(n-2))]. = 2 + (2/n)[1 - (n-1+1)/((n-1)(n-2))] = 2 + (2/n)[1 - n/((n-1)(n-2))]. = 2 + 2/n - 2/((n-1)(n-2)). Wait, check: 2 + 2/n - 2/(n(n-2)) - 2/(n(n-1)(n-2)) = 2 + 2/n - [2(n-1) + 2] / [n(n-1)(n-2)] = 2 + 2/n - 2n / [n(n-1)(n-2)] = 2 + 2/n - 2/[(n-1)(n-2)]. Yes! D_{3,n} = 2 + 2/n - 2/[(n-1)(n-2)]. Check for n=4: 2 + 2/4 - 2/(32) = 2 + 0.5 - 1/3 = 2.5 - 0.3333 = 2.16667 = 13/6. Correct! For n=5: 2 + 2/5 - 2/(43) = 2 + 0.4 - 1/6 = 2.4 - 0.16667 = 2.23333 = 67/30. Correct! For n=6: 2 + 2/6 - 2/(5*4) = 2 + 1/3 - 1/10 = 2 + 0.3333 - 0.1 = 2.23333 = 67/30. Matches our computed D_{3,6}=67/30.

So D_{3,n} = 2 + 2/n - 2/[(n-1)(n-2)].

Now D_{2,n} = 2 - 2/[n(n-1)]. D_{1,n} = 2 - 2/n.

Now D_{4,n}? Let's compute using the recurrence: D_{4,n} = 2 - 2/n + (1/n)[ D_{1,n-3} + D_{2,n-2} + D_{3,n-1} ]. Compute the sum: D_{1,n-3} = 2 - 2/(n-3). D_{2,n-2} = 2 - 2/[(n-2)(n-3)]. D_{3,n-1} = 2 + 2/(n-1) - 2/[(n-2)(n-3)]. Sum = (2+2+2) + [ -2/(n-3) - 2/[(n-2)(n-3)] + 2/(n-1) - 2/[(n-2)(n-3)] ]. = 6 + 2/(n-1) - 2/(n-3) - 4/[(n-2)(n-3)]. Then D_{4,n} = 2 - 2/n + (1/n)[ 6 + 2/(n-1) - 2/(n-3) - 4/[(n-2)(n-3)] ]. = 2 - 2/n + 6/n + 2/[n(n-1)] - 2/[n(n-3)] - 4/[n(n-2)(n-3)]. = 2 + 4/n + 2/[n(n-1)] - 2/[n(n-3)] - 4/[n(n-2)(n-3)].

Let's test for n=5 (since m=4, n must be >=4? Actually D_{4,5} corresponds to C_{4,5} - C_{4,4}. C_{4,5} is symmetric to C_{2,5}=32/5, C_{4,4}=23/6. D_{4,5} = 32/5 - 23/6 = 192/30 - 115/30 = 77/30 ≈ 2.5667. Our formula for n=5: 2 + 4/5 + 2/(54) - 2/(52) - 4/(532) = 2 + 0.8 + 0.1 - 0.2 - 4/30 = 2.7 - 0.13333 = 2.56667. 2.56667 = 77/30? 77/30 = 2.56667. Yes! For n=6: D_{4,6} = C_{4,6} - C_{4,5}. C_{4,6}=C_{3,6}=269/30, C_{4,5}=32/5=192/30. D_{4,6}=77/30? Wait 269/30 - 192/30 = 77/30. So D_{4,6}=77/30 as well? Let's check with formula: 2 + 4/6 + 2/(65) - 2/(63) - 4/(643) = 2 + 2/3 + 1/15 - 1/9 - 4/72 = 2 + 0.6667 + 0.06667 - 0.11111 - 0.05556 = 2.56667. Yes, 77/30.

Now, can we simplify D_{4,n}? D_{4,n} = 2 + 4/n + 2/[n(n-1)] - 2/[n(n-3)] - 4/[n(n-2)(n-3)]. Combine terms over common denominator? Maybe we can find a pattern.

Let's write D_{m,n} for m=1,2,3,4: m=1: 2 - 2/n = 2 - 2/n. m=2: 2 - 2/[n(n-1)]. m=3: 2 + 2/n - 2/[(n-1)(n-2)]. m=4: 2 + 4/n + 2/[n(n-1)] - 2/[n(n-3)] - 4/[n(n-2)(n-3)]? Wait, the simplified form for m=3 was 2 + 2/n - 2/[(n-1)(n-2)]. For m=4, maybe it simplifies to 2 + 4/n - 2/[(n-1)(n-2)] + something?

Let's try to simplify D_{4,n} further: D_{4,n} = 2 + 4/n + 2/[n(n-1)] - 2/[n(n-3)] - 4/[n(n-2)(n-3)]. Factor 2/n: = 2 + 2/n [2 + 1/(n-1) - 1/(n-3) - 2/((n-2)(n-3))]. Not obviously simpler.

Maybe there's a known formula for C_{mn} from the literature. I recall that the expected number of comparisons in Hoare's FIND is: C_{mn} = 2n - 2H_n + 2 \sum_{i=1}^{m-1} \frac{1}{i} + 2 \sum_{i=1}^{n-m} \frac{1}{i} - 2 \sum_{i=1}^{m-1} \frac{1}{n-i+1}? No.

Let's try to express C_{mn} in terms of harmonic numbers by summing D_{m,n}. C_{mn} = \sum_{k=m}^{n} D_{m,k} + C_{m,m}? Wait, C_{mn} is defined for m <= n. The base case is C_{mm} which is symmetric to C_{1m}? Actually C_{mm} = C_{1m} by symmetry? For n=3, C33 = C13 = 7/3. Yes, C_{nn} = C_{1n} = 2n - 2H_n. So C_{mn} = C_{mm} + \sum_{k=m+1}^{n} D_{m,k} for n > m. But we also have symmetry: C_{mn} = C_{n+1-m, n}. So we can focus on m <= (n+1)/2.

We have D_{m,n} for fixed m as a function of n. We can try to find a closed form for C_{mn} by summing D.

From the recurrence for D, we can write: n D_{m,n} = 2n - 2 + \sum_{j=1}^{m-1} D_{j, n-m+j}. This is a recurrence that can be solved by induction. Notice that the sum is over j from 1 to m-1 of D_{j, n-m+j}. This suggests that D_{m,n} can be expressed in terms of D_{j, \cdot} for smaller j.

Let's try to find an explicit formula for D_{m,n} by induction. Suppose D_{m,n} = 2 \sum_{k=0}^{m-1} a_{m,k} / (n-k)? Not sure.

Another approach: The problem is from TAOCP, and the answer is likely in the back of the book. I remember that the answer to exercise 32 is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But we saw that's O(n log n). Wait, maybe the formula is for the number of comparisons in a different model? Let's check the recurrence again. The recurrence we derived is C_{mn} = n-1 + ... and we got C_{1n} = 2n - 2H_n. That is O(n). The formula 2(n+1)H_n - ... is O(n log n). So it cannot be that.

Maybe the formula is: C_{mn} = 2n - 2H_n + 2 \sum_{i=1}^{m-1} \frac{1}{i} + 2 \sum_{i=1}^{n-m} \frac{1}{i}? That would be 2n - 2H_n + 2H_{m-1} + 2H_{n-m}. For n=3,m=2: 6 - 11/3 + 21 + 21 = 6 - 11/3 + 4 = 10 - 11/3 = 19/3 ≈ 6.333. Not 8/3.

What about C_{mn} = 2n - 2H_n + 2H_m + 2H_{n-m+1} - 2H_n? That's 2n + 2H_m + 2H_{n-m+1} - 4H_n? For n=3,m=2: 6 + 3 + 3 - 4*11/6 = 12 - 44/6 = 12 - 7.333 = 4.667. No.

Let's try to find the formula by looking at the values of C_{mn} + 2H_m + 2H_{n-m+1} or something.

Compute C_{mn} + 2H_m + 2H_{n-m+1}: n=3,m=1: C13=7/3, 2H_1=2, 2H_3=11/3. Sum = 7/3 + 2 + 11/3 = 18/3 + 2 = 6+2=8. n=3,m=2: C23=8/3, 2H_2=3, 2H_2=3. Sum = 8/3 + 6 = 8/3 + 18/3 = 26/3 ≈ 8.667. Not constant.

Maybe C_{mn} = 2n - 2H_n + 2 \sum_{k=1}^{m-1} \frac{1}{k} \frac{n-k}{n}? No.

Let's try to solve the recurrence for D_{m,n} in closed form. The recurrence is: n D_{m,n} = 2n - 2 + \sum_{j=1}^{m-1} D_{j, n-m+j}.

Let's change variables: let n = m + k, where k >= 0. Then D_{m, m+k} = 2 - 2/(m+k) + (1/(m+k)) \sum_{j=1}^{m-1} D_{j, k+j}. This is a recurrence in m for fixed k? Not exactly.

Alternatively, consider the generating function F_m(x) = \sum_{n>=m} D_{m,n} x^n. But the sum involves D_{j, n-m+j} which shifts n.

Let's try to find a pattern by computing D_{m,n} for m up to 5 and see if we can guess a general formula.

We have: D_{1,n} = 2 - 2/n. D_{2,n} = 2 - 2/[n(n-1)]. D_{3,n} = 2 + 2/n - 2/[(n-1)(n-2)]. D_{4,n} = 2 + 4/n + 2/[n(n-1)] - 2/[n(n-3)] - 4/[n(n-2)(n-3)].

Let's simplify D_{4,n} further: D_{4,n} = 2 + 4/n + 2/[n(n-1)] - 2/[n(n-3)] - 4/[n(n-2)(n-3)]. Combine the last two terms: -2/[n(n-3)] * [1 + 2/(n-2)] = -2/[n(n-3)] * [(n-2+2)/(n-2)] = -2/[n(n-3)] * n/(n-2) = -2/[(n-2)(n-3)]. So D_{4,n} = 2 + 4/n + 2/[n(n-1)] - 2/[(n-2)(n-3)]. Check for n=5: 2 + 4/5 + 2/(20) - 2/(32) = 2 + 0.8 + 0.1 - 1/3 = 2.9 - 0.3333 = 2.5667 = 77/30. Correct! For n=6: 2 + 4/6 + 2/(30) - 2/(43) = 2 + 2/3 + 1/15 - 1/6 = 2 + 0.6667 + 0.06667 - 0.16667 = 2.56667 = 77/30. Correct!

Now D_{4,n} = 2 + 4/n + 2/[n(n-1)] - 2/[(n-2)(n-3)].

Now D_{5,n}? We can compute from recurrence: D_{5,n} = 2 - 2/n + (1/n)[ D_{1,n-4} + D_{2,n-3} + D_{3,n-2} + D_{4,n-1} ]. Let's compute for general n (n>=5). D_{1,n-4} = 2 - 2/(n-4). D_{2,n-3} = 2 - 2/[(n-3)(n-4)]. D_{3,n-2} = 2 + 2/(n-2) - 2/[(n-3)(n-4)]. D_{4,n-1} = 2 + 4/(n-1) + 2/[(n-1)(n-2)] - 2/[(n-3)(n-4)]. Sum = 2+2+2+2 = 8 + [ -2/(n-4) - 2/[(n-3)(n-4)] + 2/(n-2) - 2/[(n-3)(n-4)] + 4/(n-1) + 2/[(n-1)(n-2)] - 2/[(n-3)(n-4)] ]. = 8 + 4/(n-1) + 2/(n-2) - 2/(n-4) + 2/[(n-1)(n-2)] - 6/[(n-3)(n-4)].

Then D_{5,n} = 2 - 2/n + (1/n)*Sum. = 2 - 2/n + 8/n + 4/[n(n-1)] + 2/[n(n-2)] - 2/[n(n-4)] + 2/[n(n-1)(n-2)] - 6/[n(n-3)(n-4)].

Simplify? We can test for n=5: D_{5,5} = C_{5,5} - C_{5,4}? Actually C_{5,5} = C_{1,5} = 163/30 ≈ 5.433. C_{5,4} = C_{2,4} = 9/2 = 4.5. D_{5,5} = 163/30 - 135/30 = 28/30 = 14/15 ≈ 0.9333? Wait, C_{5,4} = C_{2,4} = 9/2 = 4.5 = 135/30. C_{5,5} = 163/30. So D_{5,5} = 28/30 = 14/15 ≈ 0.9333. But our formula for D_{5,5} would have terms like 1/(n-4) which is 1/1=1. Let's plug n=5: 2 - 2/5 + 8/5 + 4/(54) + 2/(53) - 2/(51) + 2/(543) - 6/(52*1) = 2 - 0.4 + 1.6 + 0.2 + 2/15 - 0.4 + 2/60 - 6/10 = 2 + ( -0.4+1.6-0.4) = 2.8 + 2/15 + 1/30 - 0.6 = 2.2 + (4/30 + 1/30) = 2.2 + 5/30 = 2.2 + 1/6 = 2.2 + 0.16667 = 2.36667. That's not 0.9333. So my formula for D_{5,n} is wrong because I mis-summed? Let's recompute D_{5,5} directly from the recurrence: D_{5,5} = C_{5,5} - C_{5,4}. But C_{5,4} is C_{4,5}? Wait, C_{mn} is defined for m <= n. So C_{5,4} is not defined because m > n. The symmetry is C_{mn} = C_{n+1-m, n}. So for m=5, n=5, C_{5,5} = C_{1,5}. For m=4, n=5, C_{4,5} = C_{2,5} = 32/5. So D_{4,5} = C_{4,5} - C_{4,4} = 32/5 - 23/6 = 192/30 - 115/30 = 77/30. For m=5, we would need C_{5,5} and C_{5,6} etc. So D_{5,5} is not defined from our table because n starts at m. D_{m,n} is defined for n >= m. For n=m, D_{m,m} = C_{m,m} - C_{m,m-1}? But C_{m,m-1} is not defined. So the base for D is at n=m. We have C_{mm} known. So the recurrence for D_{m,n} holds for n > m. For n=m, we have the base case C_{mm} = C_{1m} = 2m - 2H_m.

So the recurrence D_{m,n} = 2 - 2/n + (1/n) \sum_{j=1}^{m-1} D_{j, n-m+j} holds for n > m. And D_{m,m} = C_{m,m} - C_{m,m-1} is not used; instead we have C_{mm} as base.

Now, we want a closed form for C_{mn}. We have C_{mn} = C_{mm} + \sum_{k=m+1}^{n} D_{m,k} for n > m.

We have expressions for D_{1,n}, D_{2,n}, D_{3,n}, D_{4,n}. They are rational functions of n. The sums of these from k=m+1 to n will yield harmonic numbers.

Let's sum D_{1,k} from k=2 to n: \sum_{k=2}^n (2 - 2/k) = 2(n-1) - 2(H_n - 1) = 2n - 2H_n. That's C_{1n}.

Sum D_{2,k} from k=3 to n: D_{2,k} = 2 - 2/[k(k-1)] = 2 - 2(1/(k-1) - 1/k) = 2 - 2/(k-1) + 2/k. Sum from k=3 to n: \sum (2) = 2(n-2). \sum -2/(k-1) = -2(H_{n-1} - 1). \sum 2/k = 2(H_n - 1 - 1/2). Total = 2n - 4 - 2H_{n-1} + 2 + 2H_n - 2 - 1 = 2n - 5 - 2H_{n-1} + 2H_n. But 2H_n - 2H_{n-1} = 2/n. So = 2n - 5 + 2/n. Then C_{2n} = C_{22} + sum = 1 + 2n - 5 + 2/n = 2n - 4 + 2/n. Check for n=3: 6 - 4 + 2/3 = 2 + 2/3 = 8/3. Correct! n=4: 8 - 4 + 1/2 = 4.5 = 9/2. Correct! n=5: 10 - 4 + 2/5 = 6.4 = 32/5. Correct! n=6: 12 - 4 + 1/3 = 8.333 = 25/3. Correct! So C_{2n} = 2n - 4 + 2/n.

Now C_{3n} for n>=3: C_{3n} = C_{33} + \sum_{k=4}^n D_{3,k}. D_{3,k} = 2 + 2/k - 2/[(k-1)(k-2)]. Sum from k=4 to n: \sum 2 = 2(n-3). \sum 2/k = 2(H_n - 1 - 1/2 - 1/3) = 2H_n - 11/3? Wait 1+1/2+1/3 = 11/6. Times 2 = 11/3. So 2H_n - 11/3. \sum -2/[(k-1)(k-2)] = -2 \sum [1/(k-2) - 1/(k-1)] from k=4 to n. = -2 [ \sum_{j=2}^{n-2} 1/j - \sum_{j=3}^{n-1} 1/j ] = -2 [ 1/2 - 1/(n-1) ] = -1 + 2/(n-1). Total sum = 2n - 6 + 2H_n - 11/3 - 1 + 2/(n-1) = 2n + 2H_n - 6 - 14/3 + 2/(n-1) = 2n + 2H_n - 32/3 + 2/(n-1). C_{33} = 7/3. C_{3n} = 7/3 + 2n + 2H_n - 32/3 + 2/(n-1) = 2n + 2H_n - 25/3 + 2/(n-1). Check for n=4: 8 + 225/12 - 25/3 + 2/3 = 8 + 25/6 - 25/3 + 2/3 = 8 + 25/6 - 23/3 = 8 + 25/6 - 46/6 = 8 - 21/6 = 8 - 3.5 = 4.5 = 9/2. Correct! n=5: 10 + 2137/60 - 25/3 + 2/4 = 10 + 137/30 - 25/3 + 1/2 = 10 + 137/30 - 250/30 + 15/30 = 10 - 98/30 = 10 - 49/15 = 150/15 - 49/15 = 101/15. Correct! n=6: 12 + 2*49/20 - 25/3 + 2/5 = 12 + 49/10 - 25/3 + 2/5 = 12 + 147/30 - 250/30 + 12/30 = 12 - 91/30 = 360/30 - 91/30 = 269/30. Correct!

So C_{3n} = 2n + 2H_n - 25/3 + 2/(n-1).

Now C_{4n} for n>=4: C_{44} = C_{14} = 23/6. D_{4,k} = 2 + 4/k + 2/[k(k-1)] - 2/[(k-2)(k-3)]. Sum from k=5 to n: \sum 2 = 2(n-4). \sum 4/k = 4(H_n - 1 - 1/2 - 1/3 - 1/4) = 4H_n - 4*(25/12) = 4H_n - 25/3. \sum 2/[k(k-1)] = 2 \sum [1/(k-1) - 1/k] = 2[1/4 - 1/n] = 1/2 - 2/n. \sum -2/[(k-2)(k-3)] = -2 \sum [1/(k-3) - 1/(k-2)] = -2[1/2 - 1/(n-2)] = -1 + 2/(n-2). Total sum = 2n - 8 + 4H_n - 25/3 + 1/2 - 2/n - 1 + 2/(n-2) = 2n + 4H_n - 8 - 25/3 - 1/2? Wait: 1/2 - 1 = -1/2. So = 2n + 4H_n - 8 - 25/3 - 1/2 - 2/n + 2/(n-2). Combine constants: -8 - 25/3 - 1/2 = -48/6 - 50/6 - 3/6 = -101/6. C_{4n} = C_{44} + sum = 23/6 + 2n + 4H_n - 101/6 - 2/n + 2/(n-2) = 2n + 4H_n - 78/6 - 2/n + 2/(n-2) = 2n + 4H_n - 13 - 2/n + 2/(n-2). Check for n=5: 10 + 4137/60 - 13 - 2/5 + 2/3 = 10 + 137/15 - 13 - 2/5 + 2/3 = -3 + 137/15 - 6/15 + 10/15 = -3 + 141/15 = -3 + 9.4 = 6.4 = 32/5. Correct! n=6: 12 + 449/20 - 13 - 2/6 + 2/4 = 12 + 49/5 - 13 - 1/3 + 1/2 = -1 + 49/5 - 1/3 + 1/2 = -1 + 294/30 - 10/30 + 15/30 = -1 + 299/30 = 269/30. Correct!

So we have: C_{1n} = 2n - 2H_n C_{2n} = 2n - 4 + 2/n C_{3n} = 2n + 2H_n - 25/3 + 2/(n-1) C_{4n} = 2n + 4H_n - 13 - 2/n + 2/(n-2)

The pattern is not immediately obvious for a general m. But notice that C_{mn} can be written as: C_{mn} = 2n + 2(m-1)H_n + ...? For m=1: coefficient of H_n is -2. m=2: 0. m=3: +2. m=4: +4. So coefficient of H_n is 2(m-2)? For m=1: -2, m=2: 0, m=3: 2, m=4: 4. That's 2m-4? For m=1: -2, m=2:0, m=3:2, m=4:4. Yes, 2m-4. But wait, for m=5 it would be 6? But the formula should be symmetric in m and n-m+1. The coefficient of H_n cannot be asymmetric. Let's check C_{n,n} = C_{1n} = 2n - 2H_n. For m=n, coefficient of H_n is -2. If coefficient is 2m-4, for m=n it would be 2n-4, which is not -2. So the expression we have for C_{3n} and C_{4n} is only valid for m fixed and n large? But we derived them exactly for all n >= m. They are exact. So for m=3, C_{3n} = 2n + 2H_n - 25/3 + 2/(n-1). This is not symmetric. But we know C_{3n} = C_{n-2, n} by symmetry? For n=5, C_{35} = C_{35}. For n=6, C_{36} = C_{46}? Actually symmetry: C_{mn} = C_{n+1-m, n}. So C_{3n} = C_{n-2, n}. For n=6, C_{36} = C_{46}. Our formula for C_{3n} gave 269/30 for n=6. C_{46} from the C_{4n} formula for n=6 gave 269/30. So they match. But the formula for C_{3n} has +2H_n, while C_{4n} has +4H_n. For n=6, C_{46} uses the formula for m=4 with n=6: 2*6 + 4H_6 - 13 - 2/6 + 2/4 = 12 + 49/5 - 13 - 1/3 + 1/2 = ... we got 269/30. If we used the symmetry, we could express C_{46} as C_{36} which uses m=3 formula with n=6. So the formulas are consistent but expressed in terms of H_n with different coefficients. That's because the formulas are not symmetric; they are valid only for m <= something? Actually, the formulas we derived are for fixed m and variable n >= m. They are exact for all n >= m. But they are not symmetric because we fixed m. If we want a symmetric formula, we need to combine them.

The problem asks for a "simple closed form expression for C_{mn}". It likely expects a formula that is symmetric in m and n-m+1, expressed in terms of harmonic numbers.

Let's look at the expressions we have: C_{1n} = 2n - 2H_n C_{2n} = 2n - 4 + 2/n C_{3n} = 2n + 2H_n - 25/3 + 2/(n-1) C_{4n} = 2n + 4H_n - 13 - 2/n + 2/(n-2)

Maybe the general formula is: C_{mn} = 2n + 2(m-2)H_n + ... but that's not symmetric.

Wait, we can express C_{mn} in terms of harmonic numbers of m and n-m+1 by using the symmetry. For m=2, C_{2n} = 2n - 4 + 2/n. By symmetry, C_{n-1, n} = C_{2n} = 2n - 4 + 2/n. So C_{n-1, n} = 2n - 4 + 2/n. If we write it as a function of m = n-1, then n = m+1, so C_{m, m+1} = 2(m+1) - 4 + 2/(m+1) = 2m - 2 + 2/(m+1). That's not obviously a simple combination of H_m.

Maybe the closed form is: C_{mn} = 2n + 2 \sum_{i=1}^{m-1} \frac{1}{i} + 2 \sum_{i=1}^{n-m} \frac{1}{i} - 2 \sum_{i=1}^{n} \frac{1}{i} + \text{something}? Let's test.

For m=2: C_{2n} = 2n + 2H_1 + 2H_{n-2} - 2H_n + ? = 2n + 2 + 2H_{n-2} - 2H_n = 2n + 2 - 2(1/(n-1) + 1/n) = 2n + 2 - 2(2n-1)/(n(n-1)). Not 2n - 4 + 2/n.

What about C_{mn} = 2n - 2H_n + 2H_m + 2H_{n-m+1} - 2? For m=2: 2n - 2H_n + 2H_2 + 2H_{n-1} - 2 = 2n - 2H_n + 3 + 2H_n - 2/n - 2 = 2n + 1 - 2/n. Not 2n - 4 + 2/n.

Maybe the formula is: C_{mn} = 2n - 2 \sum_{i=1}^{n} \frac{1}{i} + 2 \sum_{i=1}^{m} \frac{1}{i} + 2 \sum_{i=1}^{n-m+1} \frac{1}{i}? For m=1: 2n - 2H_n + 2 + 2H_n = 2n + 2. No.

Let's try to find the formula from the literature. I recall that the average number of comparisons in Hoare's FIND is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But that's for a different measure? Wait, I found a paper: "The average number of comparisons in Hoare's FIND" by Knuth? Actually, the exact formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? I'm now doubting my earlier conclusion that quickselect is O(n). The recurrence C_{mn} = n-1 + ... does yield C_{mn} = O(n log n)? Let's check: C_{1n} = 2n - 2H_n ~ 2n. That's O(n). C_{2n} = 2n - 4 + 2/n ~ 2n. C_{3n} = 2n + 2H_n ~ 2n + 2 log n. So it's O(n). The formula 2(n+1)H_n is O(n log n). So it's not that.

Maybe the formula I recalled is for the number of comparisons in quicksort when selecting the m-th element? No.

Let's search for "quickfind average comparisons closed form". I remember a result by Kirchhoff? Or maybe the formula is: C_{mn} = 2n - 2H_n + 2 \sum_{i=1}^{m-1} \frac{1}{i} \frac{n-i}{n}? No.

Wait, we can derive the general formula by solving the recurrence for D_{m,n} in closed form. The recurrence is: n D_{m,n} = 2n - 2 + \sum_{j=1}^{m-1} D_{j, n-m+j}. with D_{1,n} = 2 - 2/n.

This is a linear recurrence. We can try to find D_{m,n} by induction. Let's compute the values of D_{m,n} for fixed m as a function of n, and see if they can be expressed as 2 \sum_{k=1}^{m} \frac{(-1)^{m-k} S(m,k)}{n(n-1)...(n-k+1)}? Not sure.

Another approach: The problem is from TAOCP, and the answer is likely given in the book. I can try to recall the exact answer from the book's answer section. I think the answer is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But that's for the number of comparisons in a different algorithm? Or maybe the formula is for the average number of comparisons when finding the m-th smallest using a variant where you compare the pivot with all elements including itself? That would add n comparisons? No.

Let's check the values for C_{mn} from the formula F(m,n) = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 for n=2,m=1: 231.5 - 231.5 - 4 + 6 = 2. If we subtract 1, we get 1. For n=3,m=2: 44/3 - 9 - 9 + 8 = 14/3. If we subtract 2, we get 8/3. For n=4,m=2: 125/6 - 88/6 - 9 + 10 = 37/6 +1 = 43/6 ≈7.167. Subtract something to get 4.5=27/6. Difference = 16/6 = 8/3. Not constant.

Maybe the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2H_n? For m=1: 2n - 2? Not 2n - 2H_n.

Let's look at the expressions we derived: C_{1n} = 2n - 2H_n C_{2n} = 2n - 4 + 2/n C_{3n} = 2n + 2H_n - 25/3 + 2/(n-1) C_{4n} = 2n + 4H_n - 13 - 2/n + 2/(n-2)

Notice that the coefficients of H_n are -2, 0, 2, 4,... which is 2(m-2) for m>=1? For m=1: -2, m=2:0, m=3:2, m=4:4. That's 2m-4. The constant terms (without H_n and without rational functions of n) are: for m=1: 0? 2n - 2H_n has no constant term other than those in H_n? Actually, H_n = ln n + gamma + 1/(2n) - ... So the constant term in C_{1n} is -2gamma? But we are looking for exact closed form.

Maybe we can write C_{mn} as: C_{mn} = 2n - 2H_n + 2 \sum_{k=1}^{m-1} \frac{1}{k} + 2 \sum_{k=1}^{n-m} \frac{1}{k}? No.

Wait, I recall a known result: The expected number of comparisons in Hoare's FIND is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But we saw it's O(n log n). However, maybe the recurrence in the book has partition cost n+1? If partition cost is n+1, then C_{1n} = n+1 + (1/n) sum C_{1j}. Then n C_{1n} = n(n+1) + S_{n-1}. S_n = S_{n-1}(1+1/n) + n+1. S_1 = C_{11} = 0? If C_{11}=0, then S_2 = 3, C_{12}=3. Then S_3 = 3*(4/3)+4=4+4=8, C_{13}=5. This is not 2n+2H_n? Let's solve: S_n/(n+1) = S_{n-1}/n + (n+1)/(n+1)? Actually S_n = S_{n-1}(1+1/n) + n+1. Divide by n+1: S_n/(n+1) = S_{n-1}/n + 1. So S_n/(n+1) = n + S_1/1? S_1=0, so S_n = n(n+1). Then C_{1n} = S_n - S_{n-1} = n(n+1) - (n-1)n = 2n. So C_{1n} = 2n exactly! That's very simple. Then C_{2n} would be something else. If partition cost is n+1, then the average comparisons for quickselect might be exactly 2n for m=1? But we know that's not true for the standard quickselect; the minimum takes about 2n - 2 log n comparisons. So partition cost n+1 gives a different algorithm.

Given that our recurrence with partition cost n-1 yields C_{1n} = 2n - 2H_n, which matches the standard quickselect analysis, we should stick with that.

Now, the problem asks for a "simple closed form expression". The expressions we have for C_{mn} are: C_{mn} = 2n + 2(m-2)H_n + ... but that's not symmetric.

Maybe the symmetric closed form is: C_{mn} = 2n - 2H_n + 2H_m + 2H_{n-m+1} - 2? Let's test: For n=3,m=2: 6 - 11/3 + 3 + 3 - 2 = 10 - 11/3 = 19/3 ≈ 6.333. No. What about C_{mn} = 2n - 2H_n + 2H_m + 2H_{n-m+1} - 2H_{m} - 2H_{n-m+1} + ... No.

Let's try to find the formula by looking at the sum of D_{m,k}. We have D_{m,k} = 2 + ... The sum of D_{m,k} from k=m+1 to n gives C_{mn} - C_{mm}. We know C_{mm} = C_{1m} = 2m - 2H_m. So C_{mn} = 2m - 2H_m + \sum_{k=m+1}^n D_{m,k}.

We have formulas for D_{m,k} up to m=4. They involve terms like 1/k, 1/(k-1), etc. The sums will produce harmonic numbers and rational functions.

Maybe the general D_{m,k} can be expressed as: D_{m,k} = 2 \sum_{j=0}^{m-1} \frac{(-1)^j}{k(k-1)...(k-j)}? Not sure.

Let's look at the pattern of D_{m,n}: D_{1,n} = 2 - 2/n. D_{2,n} = 2 - 2/[n(n-1)]. D_{3,n} = 2 + 2/n - 2/[(n-1)(n-2)]. D_{4,n} = 2 + 4/n + 2/[n(n-1)] - 2/[(n-2)(n-3)].

We can write them as: D_{1,n} = 2 * (1 - 1/n) D_{2,n} = 2 * (1 - 1/[n(n-1)]) D_{3,n} = 2 * (1 + 1/n - 1/[(n-1)(n-2)]) D_{4,n} = 2 * (1 + 2/n + 1/[n(n-1)] - 1/[(n-2)(n-3)])

Maybe D_{m,n} = 2 \sum_{i=0}^{m-1} \frac{a_{m,i}}{n(n-1)...(n-i)}? Let's try to express D_{3,n} in that form: D_{3,n} = 2 + 2/n - 2/[(n-1)(n-2)] = 2 + 2/n - 2/[n(n-1)(n-2)] * n? Not a simple product.

Wait, we can express D_{3,n} as: D_{3,n} = 2 + 2/n - 2/[(n-1)(n-2)] = 2 + 2/n - 2/n * [n/[(n-1)(n-2)]]. Not helpful.

Let's try to find the generating function or solve the recurrence directly for C_{mn}. The recurrence is: n C_{mn} = n(n-1) + \sum_{j=1}^{m-1} C_{j, n-m+j} + \sum_{j=m}^{n-1} C_{m, j}.

This is a known recurrence. I recall that the solution is: C_{mn} = 2n - 2H_n + 2 \sum_{i=1}^{m-1} \frac{1}{i} + 2 \sum_{i=1}^{n-m} \frac{1}{i} - 2 \sum_{i=1}^{n} \frac{1}{i}? No.

Wait, maybe the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But that's for the number of comparisons in a different algorithm? Let me check the asymptotic behavior of that formula for median. For m = (n+1)/2, the formula gives ~ 2n log n - 2(n/2) log(n/2) - 2(n/2) log(n/2) + 2n = 2n log n - n log(n/2) - n log(n/2) + 2n = 2n log n - 2n log n + 2n log 2 + 2n = 2n(1 + log 2). That's O(n), not O(n log n)! Because the n H_n terms cancel! Let's check: 2(n+1)H_n ~ 2n log n. -2(n+2-m)H_{n-m+1} ~ -2(n/2) log(n/2) = -n log n + n log 2. -2(m+1)H_m ~ -2(n/2) log(n/2) = -n log n + n log 2. Sum = 2n log n - 2n log n + 2n log 2 = 2n log 2. Then plus 2n gives 2n(1+log 2). So it is O(n)! The n log n terms cancel out. So the formula is O(n). That's perfect! So the formula 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 is indeed O(n). I mistakenly thought it was O(n log n) because of the n H_n terms, but they cancel for m ~ n/2. For m=1, it gives 2n - 2, which is O(n). But we need to check if it matches our exact values.

Let's test the formula F(m,n) = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 for our small n values.

For n=2,m=1: 231.5 = 9. -2*(2+2-1)= -6 * H_2 = -9. -221 = -4. +2n+2=6. Total = 9 -9 -4 +6 = 2. But we have C_{12}=1. So off by 1.

For n=3,m=1: 2411/6 = 44/3. -2*(3+2-1)= -8 * H_3 = -811/6 = -44/3. -22*1 = -4. +2n+2=8. Total = 44/3 -44/3 -4 +8 = 4. We have C_{13}=7/3 ≈ 2.333. Off by 5/3? 4 - 7/3 = 5/3.

For n=3,m=2: 2411/6 = 44/3. -2*(3+2-2)= -6 * H_2 = -9. -231.5 = -9. +8. Total = 44/3 -10 = 14/3 ≈ 4.667. We have C_{23}=8/3 ≈ 2.667. Off by 2.

For n=4,m=2: 2525/12 = 125/6 ≈ 20.833. -2*(4+2-2)= -8 * H_3 = -811/6 = -88/6 ≈ -14.667. -23*1.5 = -9. +10. Total = 125/6 - 88/6 -9 +10 = 37/6 +1 = 43/6 ≈ 7.167. We have C_{24}=9/2=4.5. Off by 16/6 = 8/3 ≈ 2.667.

The differences are not constant. But maybe the formula is C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2H_n? For m=1: 2n - 2? Still not 2n - 2H_n.

Wait, maybe the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2 \sum_{i=1}^{n} \frac{1}{i}? That would subtract 2H_n. For m=1: 2n - 2H_n? Let's test: F(m,n) = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2H_n = 2n H_n + 2H_n - ... - 2H_n = 2n H_n - ... For m=1: 2n H_n - 2(n+1)H_n + 2n + 2 = -2H_n + 2n + 2? Wait: 2(n+1)H_n - 2(n+1)H_n - 4 + 2n + 2 - 2H_n = 2n - 2 - 2H_n? Not 2n - 2H_n.

Let's compute carefully: If we subtract 2H_n from the formula: For m=1: 2(n+1)H_n - 2(n+1)H_n - 4 + 2n + 2 - 2H_n = 2n - 2 - 2H_n. We need 2n - 2H_n. So off by -2.

What if we add 2? Then 2n - 2H_n. So F(m,n) - 2H_n + 2 gives 2n - 2H_n for m=1. For m=2,n=3: F(2,3) = 14/3. F - 2H_3 + 2 = 14/3 - 11/3 + 2 = 1 + 2 = 3. But C23=8/3. Not match.

Maybe the correct formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2 \sum_{i=1}^{m} \frac{1}{i} - 2 \sum_{i=1}^{n-m+1} \frac{1}{i} + 2 \sum_{i=1}^{n} \frac{1}{i}? That would be symmetric.

Let's try to derive the formula from the recurrence using the method of "summation factors". We have the recurrence for C_{mn}. We already found D_{m,n} and C_{mn} for small m. Let's try to find a general expression for C_{mn} by guessing the form from the literature.

I recall a paper: "On the average number of comparisons in Hoare's FIND" by Mahmoud, 1991. The formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2? But we saw it doesn't match our small n. However, maybe the recurrence in that paper has a different base case or different partitioning cost. Let's check the recurrence in that paper. Hoare's FIND algorithm: the number of comparisons is n+1? Or maybe the algorithm does a comparison to check if the subarray size is 1?

Let's re-read the exercise: "For simplicity, let M = 1; that is, don't assume the use of a special technique for short subfiles." This suggests that the algorithm has a parameter M for the cutoff. In quicksort, M is the size below which you use insertion sort. If M=1, you don't use insertion sort, so you recurse down to size 1. The partitioning cost might be n+1? Or maybe the standard quicksort in Knuth uses a different partitioning that costs n+1 comparisons? In the analysis of quicksort in TAOCP, the average number of comparisons is 2(n+1)H_n - 4n? That formula gives for n=2: 231.5 - 8 = 1. So partition cost is n-1? But we saw that recurrence with n-1 gives C_2=1. The formula 2(n+1)H_n - 4n matches that recurrence. So quicksort uses n-1.

Then quickselect should use n-1. Our recurrence is correct.

Now, the formula F(m,n) = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 does not match our values. But maybe I miscomputed C_{12}? Let's double-check the algorithm for n=2. To find the smallest of 2 elements, you compare them once. That's 1 comparison. Could there be an extra comparison? In some implementations, you might compare the pivot with all elements including itself? That would be 2 comparisons. But that's silly.

Maybe the "quickfind" method in exercise 31 is not exactly Hoare's FIND but a different adaptation? Exercise 31 says: "Show that quicksort can be adapted to this purpose, avoiding many of the computations required to do a complete sort." It might be that you sort the array using quicksort but only recurse on the side containing the m-th element. The partitioning step in quicksort (Algorithm Q) might have a different number of comparisons. Let's look at the MIX program for Algorithm Q in the book. I don't have it, but I know that in Knuth's Algorithm Q, the partitioning loop does a comparison for each element, and it might do an extra comparison at the end. The total comparisons might be n+1? Actually, in the standard Hoare partition, the number of comparisons is n+1 on average? I'm not sure.

Let's check the formula 2(n+1)H_n - 4n for quicksort. For n=2, it gives 1. So quicksort on 2 elements takes 1 comparison. That matches partition cost n-1. So quicksort uses n-1.

Then why does the formula F(m,n) not match? Maybe the formula is: C_{mn} = 2(n+1)H_n - 2(n+2-m)H_{n-m+1} - 2(m+1)H_m + 2n + 2 - 2 \sum_{i=1}^{n} \frac{1}{i}? No.

Let's search for "quickfind average comparisons 2n - 2H_n". That is the formula for m=1. For m=2, we got C_{2n} = 2n - 4 + 2/n. Can we write that in terms of harmonic numbers? 2n - 4 + 2/n = 2n - 2H_n + 2H_{n-1}? 2H_{n-1} = 2H_n - 2/n. So 2n - 2H_n + 2H_n - 2/n - 4 + 2/n = 2n - 4. No.

What about C_{2n} = 2n - 2H_n + 2H_2 + 2H_{n-1} - 2? 2H_2=3, 2H_{n-1}=2H_n - 2/n. Then 2n - 2H_n + 3 + 2H_n - 2/n - 2 = 2n + 1 - 2/n. Not 2n - 4 + 2/n.

Maybe the formula is: C_{mn} = 2n + 2 \sum_{i=1}^{m-1} \frac{n-i+1}{i}? No.

Let's try to find the pattern by expressing C_{mn} in terms of H_m and H_{n-m+1}. For m=1: C_{1n} = 2n - 2H_n. For m=2: C_{2n} = 2n - 4 + 2/n. For m=3: C_{3n} = 2n + 2H_n - 25/3 + 2/(n-1). For m=4: C_{4n} = 2n + 4H_n - 13 - 2/n + 2/(n-2).

We can also write C_{mn} for m close to n using symmetry. For example, C_{n-1,n} = C_{2n} = 2n - 4 + 2/n. If we set m = n-1, then C_{n-1,n} = 2n - 4 + 2/n = 2(m+1) - 4 + 2/(m+1) = 2m - 2 + 2/(m+1). That's not a simple function of H_m.

Maybe the general formula is: C_{mn} = 2n - 2H_n + 2H_m + 2H_{n-m+1} - 2 \sum_{i=1}^{m} \frac{1}{i} \frac{1}{n-i+1}? No.

Let's try to solve the recurrence using the method of "difference" with respect to both m and n. We already have the recurrence for D_{m,n} = C_{m,n} - C_{m,n-1}. We also have the recurrence for E_{m,n} = C_{m,n} - C_{m-1,n}. By symmetry, E_{m,n} = -D_{n+1-m, n}? Not exactly.

From our computed D_{m,n}, we can try to find a closed form for D_{m,n}. Let's list D_{m,n} for m=1..4: m=1: 2 - 2/n. m=2: 2 - 2/[n(n-1)]. m=3: 2 + 2/n - 2/[(n-1)(n-2)]. m=4: 2 + 4/n + 2/[n(n-1)] - 2/[(n-2)(n-3)].

We can write them as: D_{1,n} = 2 - 2/n. D_{2,n} = 2 - 2/[n(n-1)]. D_{3,n} = 2 + 2/n - 2/[(n-1)(n-2)] = 2 + 2/n - 2/(n-1) + 2/(n-2)? No, 2/[(n-1)(n-2)] = 2/(n-2) - 2/(n-1). So D_{3,n} = 2 + 2/n - 2/(n-2) + 2/(n-1). Check: 2 + 2/n + 2/(n-1) - 2/(n-2). For n=4: 2 + 2/4 + 2/3 - 2/2 = 2 + 0.5 + 0.6667 - 1 = 2.1667 = 13/6. Correct! For n=5: 2 + 2/5 + 2/4 - 2/3 = 2 + 0.4 + 0.5 - 0.6667 = 2.2333 = 67/30. Correct! So D_{3,n} = 2 + 2/n + 2/(n-1) - 2/(n-2).

Now D_{4,n} = 2 + 4/n + 2/[n(n-1)] - 2/[(n-2)(n-3)]. We can write 2/[n(n-1)] = 2/(n-1) - 2/n. And -2/[(n-2)(n-3)] = -2/(n-3) + 2/(n-2). So D_{4,n} = 2 + 4/n + 2/(n-1) - 2/n - 2/(n-3) + 2/(n-2) = 2 + 2/n + 2/(n-1) + 2/(n-2) - 2/(n-3). Check for n=5: 2 + 2/5 + 2/4 + 2/3 - 2/2 = 2 + 0.4 + 0.5 + 0.6667 - 1 = 2.5667 = 77/30. Correct! For n=6: 2 + 2/6 + 2/5 + 2/4 - 2/3 = 2 + 1/3 + 0.4 + 0.5 - 0.6667 = 2 + 0.3333 + 0.4 + 0.5 - 0.6667 = 2.5666. Correct!

Now D_{1,n} = 2 - 2/n = 2 + 2/n? No, 2 - 2/n. But we can write D_{1,n} = 2 + 2/n? No, it's 2 - 2/n. D_{2,n} = 2 - 2/[n(n-1)] = 2 + 2/n - 2/(n-1)? Because 2/n - 2/(n-1) = (2(n-1) - 2n)/[n(n-1)] = -2/[n(n-1)]. So D_{2,n} = 2 + 2/n - 2/(n-1). Check: 2 + 2/n - 2/(n-1). For n=3: 2 + 2/3 - 2/2 = 2 + 0.6667 - 1 = 1.6667 = 5/3. Correct! So D_{2,n} = 2 + 2/n - 2/(n-1).

Now D_{3,n} = 2 + 2/n + 2/(n-1) - 2/(n-2). D_{4,n} = 2 + 2/n + 2/(n-1) + 2/(n-2) - 2/(n-3).

Pattern! D_{m,n} = 2 + 2 \sum_{i=0}^{m-2} \frac{1}{n-i} - \frac{2}{n-m+1}? Let's check: For m=1: sum from i=0 to -1 is empty, so D = 2 - 2/n? The pattern would give 2 - 2/(n-1+1)? For m=1, n-m+1 = n. So 2 - 2/n. Matches! For m=2: 2 + 2/n - 2/(n-1). Matches! For m=3: 2 + 2/n + 2/(n-1) - 2/(n-2). Matches! For m=4: 2 + 2/n + 2/(n-1) + 2/(n-2) - 2/(n-3). Matches!

So the general formula for D_{m,n} (for n > m) is: D_{m,n} = 2 + 2 \sum_{i=0}^{m-2} \frac{1}{n-i} - \frac{2}{n-m+1}. For m=1, the sum is empty, so D_{1,n} = 2 - 2/n. (Since n-m+1 = n, and -2/(n) matches.) For m>=2, sum from i=0 to m-2 of 1/(n-i) = H_n - H_{n-m+1}. So D_{m,n} = 2 + 2(H_n - H_{n-m+1}) - \frac{2}{n-m+1}. Simplify: D_{m,n} = 2 + 2H_n - 2H_{n-m+1} - \frac{2}{n-m+1}.

But wait, for m=2: D_{2,n} = 2 + 2H_n - 2H_{n-1} - 2/(n-1) = 2 + 2/n - 2/(n-1). Yes, because 2H_n - 2H_{n-1} = 2/n. For m=3: 2 + 2H_n - 2H_{n-2} - 2/(n-2) = 2 + 2/n + 2/(n-1) - 2/(n-2). Yes.

So the formula for D_{m,n} is: D_{m,n} = 2 + 2H_n - 2H_{n-m+1} - \frac{2}{n-m+1}, for n > m.

Now we can compute C_{mn} for n > m by summing D_{m,k} from k=m+1 to n, and adding C_{mm}. C_{mm} = C_{1m} = 2m - 2H_m (by symmetry). So for n >= m: C_{mn} = C_{mm} + \sum_{k=m+1}^{n} D_{m,k} = 2m - 2H_m + \sum_{k=m+1}^{n} \left( 2 + 2H_k - 2H_{k-m+1} - \frac{2}{k-m+1} \right).

Let's compute this sum. \sum_{k=m+1}^{n} 2 = 2(n-m). \sum_{k=m+1}^{n} 2H_k = 2 \sum_{k=m+1}^{n} H_k. \sum_{k=m+1}^{n} (-2H_{k-m+1}) = -2 \sum_{j=2}^{n-m+1} H_j. (Let j = k-m+1) \sum_{k=m+1}^{n} (-2/(k-m+1)) = -2 \sum_{j=2}^{n-m+1} 1/j = -2(H_{n-m+1} - 1).

So C_{mn} = 2m - 2H_m + 2(n-m) + 2 \sum_{k=m+1}^{n} H_k - 2 \sum_{j=2}^{n-m+1} H_j - 2(H_{n-m+1} - 1).

Simplify: 2m - 2H_m + 2n - 2m = 2n - 2H_m. So C_{mn} = 2n - 2H_m + 2 \sum_{k=m+1}^{n} H_k - 2 \sum_{j=2}^{n-m+1} H_j - 2H_{n-m+1} + 2.

Now we need to evaluate \sum_{k=m+1}^{n} H_k. There is a known formula: \sum_{k=1}^{N} H_k = (N+1)H_N - N. So \sum_{k=m+1}^{n} H_k = \sum_{k=1}^{n} H_k - \sum_{k=1}^{m} H_k = (n+1)H_n - n - [(m+1)H_m - m] = (n+1)H_n - (m+1)H_m - n + m.

Similarly, \sum_{j=2}^{n-m+1} H_j = \sum_{j=1}^{n-m+1} H_j - H_1 = (n-m+2)H_{n-m+1} - (n-m+1) - 1 = (n-m+2)H_{n-m+1} - n + m - 2.

Plug these in: C_{mn} = 2n - 2H_m + 2[ (n+1)H_n - (m+1)H_m - n + m ] - 2[ (n-m+2)H_{n-m+1} - n + m - 2 ] - 2H_{n-m+1} + 2.

Simplify step by step: = 2n - 2H_m + 2(n+1)H_n - 2(m+1)H_m - 2n + 2m - 2(n-m+2)H_{n-m+1} + 2n - 2m + 4 - 2H_{n-m+1} + 2.

Combine constants: 2n - 2n + 2n = 2n. (2n - 2n + 2n = 2n) 2m - 2m = 0. Constants: 4 + 2 = 6.

H_m terms: -2H_m - 2(m+1)H_m = -2(m+2)H_m. H_n terms: +2(n+1)H_n. H_{n-m+1} terms: -2(n-m+2)H_{n-m+1} - 2H_{n-m+1} = -2(n-m+3)H_{n-m+1}.

So C_{mn} = 2n + 6 + 2(n+1)H_n - 2(m+2)H_m - 2(n-m+3)H_{n-m+1}.

But wait, we have an extra +6? Let's check for m=1: C_{1n} = 2n + 6 + 2(n+1)H_n - 2(3)H_1 - 2(n-1+3)H_{n-1+1} = 2n + 6 + 2(n+1)H_n - 6 - 2(n+2)H_n = 2n + 2(n+1)H_n - 2(n+2)H_n = 2n - 2H_n. The +6 and -6 cancel! So the +6 is correct and cancels for m=1. Check for m=2: C_{2n} = 2n + 6 + 2(n+1)H_n - 2(4)H_2 - 2(n-2+3)H_{n-1} = 2n + 6 + 2(n+1)H_n - 8*(3/2) - 2(n+1)H_{n-1}. H_2 = 3/2, so 8*1.5=12. So = 2n + 6 - 12 + 2(n+1)H_n - 2(n+1)H_{n-1} = 2n - 6 + 2(n+1)(H_n - H_{n-1}) = 2n - 6 + 2(n+1)/n = 2n - 6 + 2 + 2/n = 2n - 4 + 2/n. Matches!

Check for m=3: C_{3n} = 2n + 6 + 2(n+1)H_n - 2(5)H_3 - 2(n-3+3)H_{n-2} = 2n + 6 + 2(n+1)H_n - 10H_3 - 2n H_{n-2}. H_3 = 11/6, so 1011/6 = 110/6 = 55/3 ≈ 18.333. So = 2n + 6 - 55/3 + 2(n+1)H_n -