You can surely beat that by an awful lot, since sorting algorithms only take n lg n comparisons, and a comparison takes one min and one max. Or maybe I'm misunderstanding the question as usual. If k is smallish, you can keep a list of the top k, and then to add each new element takes at most lg k comparisons, so that sounds like you can at least do it in (n-k) * lg k steps, which beats n lg n by a little. --Joshua On Thu, Oct 1, 2009 at 7:31 PM, David Wilson <davidwwilson@comcast.net> wrote:
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.
Is it possible to do better?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun