From conrado@lsi.upc.es Wed Jul 23 10:06:21 1997
From: Conrado Martinez Parra <conrado@lsi.upc.es>
Subject: open problem
To: Philippe.Flajolet@inria.fr (Philippe Flajolet)
Date: Wed, 23 Jul 1997 10:06:15 +0200 (MET DST)
X-Mailer: ELM [version 2.4 PL25 PGP2]
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit

Hi Philippe,

The second open problem that I presented in Dagstuhl was

"Let $C_n$ be the number of comparisons made by quicksort to sort
a random permutation of $\{1,\ldots,n\}$, when using the median of a
sample of size $2t+1$ to perform the partitions and the recursive
calls stop at subfiles of size $M\ge 2t+1$.  Both $M$ are $t$ are constants.
Compute the expected value of $C_n$ for all $M$ and $t$."

I was told that this one was already solved. I think there was
misunderstanding, I didn't make clear enough which was the problem.
I was pretty sure that the problem was not solve, and Bob Sedgewick has
confirmed my impression.

I was aware of the exact analysis for $t=0$ (basic algorithm) and
$t=1$ (median-of-three variant).  But the exact analysis is missing
for larger $t$. There are asymptotic analyses for the case where $t>1$,
but they only provide the main order term.  Thus even an asymptotic
analysis providing the linear term with the exact dependence on both
$M$ and $t$ will be very interesting.

Best regards, Conrado.