Recurrence relation quicksort median-of-three

Question

I am looking for a recurrence relation that describes the average number of comparisons of the quicksort algorithm considering an input array of size $n$. If the pivot element is picked randomly, the number of comparisons can be described by \begin{align} C_n=n+1+\frac{2}{n}\sum_{i=0}^{n-1} C_i \end{align} (The relation can be found for example on Wikipedia or „Concrete Mathematics“)

However, I am looking for a recurrence when the pivot element is picked by the „median of three“ strategy. This strategy considers the first, last and middle element of an array (for more information, look for example at this post). I could not find one, I‘m thankful for any help.

Answer 1

It takes $3$ comparisons to determine the median of the three elements. However, we can set the pointers to the second and second-last element and thus save two comparisons. So, we need $n+2$ comparisons before we execute quicksort on the two new arrays. Since we can assume that the three elements for the median are picked randomly, there are $k(n-k-1)$ scenarios that lead to a left array of size $k$ and a right array of size $n-k-1$. Each scenario is equally likely, thus, we have to divide by \begin{align} \sum_{k=1}^{n-2}k(n-k-1)=\frac{n(n-1)(n-2)}{6} \end{align} The final recurrence relation describing the number of comparisons is \begin{align} C_n=&n+2+\frac{6}{n(n-1)(n-2)}\sum_{k=1}^{n-2}k(n-k-1)(C_k+C_{n-k-1})\\ =&n+2+\frac{12}{n(n-1)(n-2)}\sum_{k=1}^{n-2}k(n-k-1)C_k \end{align} The recurrence can be simplified to \begin{align} (n+1)(n+2)C_{n+2}-2(n-1)(n+1)C_{n+1}+(n + 2) (n - 5)C_n=&6 (2 n + 3) \end{align} Wolfram Alpha gives the solution \begin{align} C(n) = \frac{n + 1}{7}(c_1 +12 H_n) + \frac{720 c_2}{(n - 5) (n - 4) (n - 3) (n - 2) (n - 1) n} - \frac{54}{49} n - \frac{19}{49} \end{align}