<p><a href="http://www.cs.hut.fi/~cessu/" rel="noreferrer">Kenneth Oksanen</a> has published an <a href="http://www.cs.hut.fi/~cessu/selection/" rel="noreferrer">expanded table</a> of values up to $n=15$, based on his own <a href="http://www.cs.hut.fi/~cessu/selection/selgen.c.html" rel="noreferrer">computer search</a>.  Okansen also provides descriptions of the optimal comparison trees for most of the values he reports.  Here's a screenshot of his table:</p>

<p><img src="https://i.sstatic.net/rLJYJ.png" alt="Kenneth Oksanen&#39;s bounds for selection"></p>

<p>Thanks to @MarkusBläser for the lead!</p>

CC BY-SA 3.0
2012-08-13T11:51:06.350Z
2012-08-13T11:51:06.350Z
Jeffε
<p>I wonder if this piece of information might be useful to you. Unfortunately it does not provide any additional information to the question of this post, but is rather more in reply to your comment about what this was for (analyzing variants of QuickSelect).</p>

<p>The expected minimum number of comparisons, noted $v(n,t)$ or $v_t(n)$ is of course significantly easier to compute (with expectation taken uniformly over all permutations),
$$v_t(n)=n+\min(t,n-t)+\text{l.o.t.}.$$</p>

<p>This result is not infrequently used, and in particular is the basis for the algorithms in <a href="http://dl.acm.org/citation.cfm?id=982856" rel="nofollow">"Adaptive Sampling for QuickSelect" by Martínez, Panario and Viola</a>. The starting point of the paper is QuickSelect median-of-three, and then to ask: is it pertinent to systematically pick the median, when the element we seek has a relative rank much lower than n/2 or much higher than n/2?</p>

<p>In other words, suppose you are looking for the $k$-th element in a list of $n$ elements, and you are choosing your pivot from clusters of $m$ elements. Instead of taking the median ($m/2$), you will take $\alpha m$ where $\alpha = k/n$. They show this algorithm can, for the right choice of $m$ be practically more efficient than the median-of-three variant.</p>

CC BY-SA 3.0
2012-08-17T15:41:14.743Z
2012-08-17T18:10:04.420Z
2012-08-17T18:10:04.420Z
Jérémie
<p>Volume III of Knuth's <em>The Art of Computer Programming</em> (chapter 5, verse 3.2) includes the following table listing the <em>exact</em> minimum number of comparisons required to select the $t$th smallest element from an unsorted set of size $n$, for all $1\le t \le n\le 10$.  This table, along with the well-known closed-form expressions $V_1(n) = n-1$ and $V_2(n) = n - 2 + \lceil n/2 \rceil$, represents <em>most</em> of the state of the art <strong>as of 1976</strong>.</p>

<p><img src="https://i.sstatic.net/lEBNQ.png" alt="Table from Knuth III:5.3.2"></p>

<p>Have any more <em>exact</em> values of $V_t(n)$ been computed in the last 36 years?  I'm particularly interested in exact values of $M(n) = V_{\lceil n/2 \rceil}(n)$, the minimum number of comparisons required to compute the median.</p>

<hr>

<p>As @MarkusBläser points out, Knuth's table seems to already incorporate more recent results from Bill Gasarch, Wayne Kelly, and Bill Pugh (<a href="http://dl.acm.org/citation.cfm?id=235772" rel="noreferrer">Finding the ith largest of n for small i,n</a>. <em>SIGACT News</em> 27(2):88-96, 1996.)</p>

CC BY-SA 3.0
2012-08-09T18:38:05.330Z
relevant? http://epubs.siam.org/doi/abs/10.1137/S0895480199353895
Sasho Nikolov
CC BY-SA 3.0
2012-08-09T18:58:50.173Z
Dor and Zwick's paper describes the best _asymptotic_ results known for finding the median: $(2 + 2^{-80})n \le M(n) \le 2.95 n$.  I'm more interested in _exact_ values for small $n$.  But it does include a reference to David Kirkpatrick's 1974 PhD thesis, which includes an exact bound for $V_3(n)$ for sufficiently large $n$ that I didn't notice before (and which Knuth didn't cite).
Jeffε
CC BY-SA 3.0
2012-08-09T19:11:21.213Z
Actually, Knuth _does_ cite Kirkpatrick's thesis, but claims a weaker result than Dor and Zwick.  Specifically, Kirkpatrick's results imply exact values of $V_3(n)$ for infinitely many $n$.
Jeffε
CC BY-SA 3.0
2012-08-10T23:00:27.783Z
The most famous paper on the topic, I think, is that of Pratt and Yao (1976) who are credited with being among the first to have found some (adversarial) technique to prove lowerbounds on this problem. If I were to find recent papers on the subject, I would follow [citations made to this paper](http://scholar.google.com/scholar?cites=15705692359639089062&as_sdt=2005&sciodt=0,5&hl=en). The most recent paper is Dor and Zwick's, but there is also a 1996 survey by Paterson (though I have not looked to see if it concerns itself with exact results or not).
Jérémie
CC BY-SA 3.0
2012-08-12T13:19:54.620Z
Patterson's survey is excellent, but it focuses on asymptotic results for large $n$.
Jeffε
CC BY-SA 3.0
2012-08-12T20:46:59.327Z
Nitpicking: In the last sentence in the question, you probably meant the ceiling instead of the floor.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-13T02:07:17.847Z
I just added the known values of $M(n)$ as a sequence on [OEIS](https://oeis.org/A215476).
Jeffε
CC BY-SA 3.0
2012-08-13T03:50:57.923Z
Jeff, curious why you are interested in the exact answer.
Chandra Chekuri
CC BY-SA 3.0
2012-08-13T10:47:05.267Z
Some nitpicking: I think the table already contains the results by Gasarch, Kelly, Pugh from 1996 (SIGACT News 27, 2)
Markus Bläser
CC BY-SA 3.0
2012-08-13T10:50:52.470Z
Kenneth Oksanen wrote an efficient code for computing $V_i(n)$. Unfortunately, there is only an abstract available http://www.sciencedirect.com/science/article/pii/S1571065306001582 Two years ago, one of my students send him an email and got the code from him. I do not remember whether some new values could be obtained.
Markus Bläser
CC BY-SA 3.0
2012-08-13T11:26:10.927Z
@ChandraChekuri: I'm playing around with variants of the [Blum-Floyd-Pratt-Rivest-Tarjan linear-time selection algorithm](http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm), as a potential algorithms homework problem.  If we use the minimum-comparison algorithm to find the median in each block, then what block size gives us the best constant in the big-Oh?  9 is better than 7 is better than 5; what about 11?
Jeffε
CC BY-SA 3.0
2012-08-13T22:45:53.353Z
@MarkusBläser: thanks for the great reference!!
Jérémie
CC BY-SA 3.0
2012-09-06T15:15:57.700Z
can someone indicate if the sorting graphs are (presumably) DAGs? (or trees?) and is there some discussion of the effect of the difference anywhere?
vzn
<ds.algorithms><reference-request><co.combinatorics><sorting><selection>
Exact number of comparisons to compute the median
Jeffε
# Exact number of comparisons to compute the median

(Asked by: username_0 on 2012-08-09)

Volume III of Knuth's *The Art of Computer Programming* (chapter 5, verse 3.2) includes the following table listing the *exact* minimum number of comparisons required to select the $t$th smallest element from an unsorted set of size $n$, for all $1\le t \le n\le 10$. This table, along with the well-known closed-form expressions $V\_1(n) = n-1$ and $V\_2(n) = n - 2 + \lceil n/2 \rceil$, represents *most* of the state of the art **as of 1976**.

![Table from Knuth III:5.3.2](https://i.sstatic.net/lEBNQ.png)

Have any more *exact* values of $V\_t(n)$ been computed in the last 36 years? I'm particularly interested in exact values of $M(n) = V\_{\lceil n/2 \rceil}(n)$, the minimum number of comparisons required to compute the median.

---

As @MarkusBläser points out, Knuth's table seems to already incorporate more recent results from Bill Gasarch, Wayne Kelly, and Bill Pugh ([Finding the ith largest of n for small i,n](http://dl.acm.org/citation.cfm?id=235772). *SIGACT News* 27(2):88-96, 1996.)

**Tags:** ds.algorithms, reference-request, co.combinatorics, sorting, selection

> **Comments:**
> **username_1**: relevant? http://epubs.siam.org/doi/abs/10.1137/S0895480199353895  
> **username_0**: Dor and Zwick's paper describes the best _asymptotic_ results known for finding the median: $(2 + 2^{-80})n \le M(n) \le 2.95 n$.  I'm more interested in _exact_ values for small $n$.  But it does include a reference to David Kirkpatrick's 1974 PhD thesis, which includes an exact bound for $V_3(n)$ for sufficiently large $n$ that I didn't notice before (and which Knuth didn't cite).  
> **username_0**: Actually, Knuth _does_ cite Kirkpatrick's thesis, but claims a weaker result than Dor and Zwick.  Specifically, Kirkpatrick's results imply exact values of $V_3(n)$ for infinitely many $n$.  
> **username_2**: The most famous paper on the topic, I think, is that of Pratt and Yao (1976) who are credited with being among the first to have found some (adversarial) technique to prove lowerbounds on this problem. If I were to find recent papers on the subject, I would follow [citations made to this paper](http://scholar.google.com/scholar?cites=15705692359639089062&as_sdt=2005&sciodt=0,5&hl=en). The most recent paper is Dor and Zwick's, but there is also a 1996 survey by Paterson (though I have not looked to see if it concerns itself with exact results or not).  
> **username_0**: Patterson's survey is excellent, but it focuses on asymptotic results for large $n$.  
> **username_3**: Nitpicking: In the last sentence in the question, you probably meant the ceiling instead of the floor.  
> **username_0**: I just added the known values of $M(n)$ as a sequence on [OEIS](https://oeis.org/A215476).  
> **username_4**: Jeff, curious why you are interested in the exact answer.  
> **username_5**: Some nitpicking: I think the table already contains the results by Gasarch, Kelly, Pugh from 1996 (SIGACT News 27, 2)  
> **username_5**: Kenneth Oksanen wrote an efficient code for computing $V_i(n)$. Unfortunately, there is only an abstract available http://www.sciencedirect.com/science/article/pii/S1571065306001582 Two years ago, one of my students send him an email and got the code from him. I do not remember whether some new values could be obtained.  
> **username_0**: @ChandraChekuri: I'm playing around with variants of the [Blum-Floyd-Pratt-Rivest-Tarjan linear-time selection algorithm](http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm), as a potential algorithms homework problem.  If we use the minimum-comparison algorithm to find the median in each block, then what block size gives us the best constant in the big-Oh?  9 is better than 7 is better than 5; what about 11?  
> **username_2**: @MarkusBläser: thanks for the great reference!!  
> **username_6**: can someone indicate if the sorting graphs are (presumably) DAGs? (or trees?) and is there some discussion of the effect of the difference anywhere?  

---

## 2 answers

### Answer by username_0 on 2012-08-13. Score: 17

[Kenneth Oksanen](http://www.cs.hut.fi/~cessu/) has published an [expanded table](http://www.cs.hut.fi/~cessu/selection/) of values up to $n=15$, based on his own [computer search](http://www.cs.hut.fi/~cessu/selection/selgen.c.html). Okansen also provides descriptions of the optimal comparison trees for most of the values he reports. Here's a screenshot of his table:

![Kenneth Oksanen's bounds for selection](https://i.sstatic.net/rLJYJ.png)

Thanks to @MarkusBläser for the lead!


---

### Answer by username_2 on 2012-08-17. Score: 3

I wonder if this piece of information might be useful to you. Unfortunately it does not provide any additional information to the question of this post, but is rather more in reply to your comment about what this was for (analyzing variants of QuickSelect).

The expected minimum number of comparisons, noted $v(n,t)$ or $v\_t(n)$ is of course significantly easier to compute (with expectation taken uniformly over all permutations),
$$v\_t(n)=n+\min(t,n-t)+\text{l.o.t.}.$$

This result is not infrequently used, and in particular is the basis for the algorithms in ["Adaptive Sampling for QuickSelect" by Martínez, Panario and Viola](http://dl.acm.org/citation.cfm?id=982856). The starting point of the paper is QuickSelect median-of-three, and then to ask: is it pertinent to systematically pick the median, when the element we seek has a relative rank much lower than n/2 or much higher than n/2?

In other words, suppose you are looking for the $k$-th element in a list of $n$ elements, and you are choosing your pivot from clusters of $m$ elements. Instead of taking the median ($m/2$), you will take $\alpha m$ where $\alpha = k/n$. They show this algorithm can, for the right choice of $m$ be practically more efficient than the median-of-three variant.


---

