From: "David Wilson" <davidwwilson@comcast.net>
Let f(n, k) be the number of binary min and max operations required to find the kth largest of n integers.
One way to find f(n, k) is to take the min over all of the maxes of subsets of k elements in A. This proves f(n, k) <= n C(n-1, k-1) - 1.
Or if k > n/2, take the max of the mins of (n-k)...
Is it possible to do better?
[mentions of linear median/select] (& later)
I'm not talking about an algorithm, but a fixed expression.
You can take a sorting network as in http://en.wikipedia.org/wiki/Sorting_network and convert it to the kind of expression you're looking for, by replicating every reused expression (and sub...expression). In that way, the problem converts to optimizing sorting networks for a new cost function. --Steve