Exercise 1.14
Solve the following recurrence:
All that is needed is this nifty little identity:
It’s not clear that $A_0=0$, but if it is, then $A_N=N$.
Exercise 1.15
Show that the average number of exchanges used during the first partitioning stage (before the pointers cross) is $(N−2)/6$.
This is harder than it sounds. I used hand-waving to say that we chip away at both the left-hand and right-hand sides by an “average run” of numbers less than or greater than the pivot. If the keys are random, they are equally likely to be greater than or less than the pivot. So the “average run” is like an average run of consecutive heads in a coin toss experiment, which is $1/(1-p)$ or $2$. So typically we will chip away two from each end and then the exchange itself chips away one more so we typically chip away six keys per exchange. The “minus two” is because before the pointers cross there is no exchange if $N \leqslant 2$.
Exercise 1.17
If we change the first line in the quicksort implementation above to call insertion sort when hi-lo <= M then the total number of comparisons to sort $N$ elements is described by the recurrence…
The expression is already closed-form for $N \leqslant M$, so we just need an expression for $N \gt M$. The solution is identical to the pure-quicksort until the telescoping at which point the constant portion is $C_M$ and the harmonic sum starts later so $H_M$ needs to be subtracted.
Exercise 1.18
Ignoring small terms (those significantly less than $N$) in the answer to the previous exercise, find a function $f(M)$ so that the number of comparisons is approximately $2N \ln N+f(M)N$. Plot the function $f(M)$, and find the value of $M$ that minimizes the function.
So $f(M)=\frac{M ( M-1 )}{4 ( M+1 )} -2H_{M+1}$ and replacing the harmonic number by its approximation yields a differentiable expression that is solvable as a quadratic with the result that the number of comparisons is minimized when $M=3 \left( \sqrt{2} +1 \right)$ or about $7$.