There are linear time selection algorithms (i.e. running time O(n) where the constant in the O is absolute and doesn't depend on k), which, I'm sure can be adapted to using just max and min. For example look at the wikipedia article on selection algorithms http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_al... for references. Victor On Thu, Oct 1, 2009 at 10: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