Skip to main content
Tweeted twitter.com/StackCSTheory/status/744650428906934272
added 11 characters in body
Source Link

Quicksort: compute the expected number of comparisons for allas a function of $M$ and $t$

I stumbled upon this problem on a list of open problems in the analysis of algorithms dating back to 1997. Is it still open? Can anyone point to a reference with a full or partial solution, or at least discussion?

Problem description (see link for more context):

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[as a function of] $M$ and $t$.

Quicksort: compute the expected number of comparisons for all $M$ and $t$

I stumbled upon this problem on a list of open problems in the analysis of algorithms dating back to 1997. Is it still open? Can anyone point to a reference with a full or partial solution, or at least discussion?

Problem description (see link for more context):

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$.

Quicksort: compute the expected number of comparisons as a function of $M$ and $t$

I stumbled upon this problem on a list of open problems in the analysis of algorithms dating back to 1997. Is it still open? Can anyone point to a reference with a full or partial solution, or at least discussion?

Problem description (see link for more context):

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$ [as a function of] $M$ and $t$.

Source Link

Quicksort: compute the expected number of comparisons for all $M$ and $t$

I stumbled upon this problem on a list of open problems in the analysis of algorithms dating back to 1997. Is it still open? Can anyone point to a reference with a full or partial solution, or at least discussion?

Problem description (see link for more context):

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$.