On Mon, Jul 6, 2009 at 4:32 PM, Matthias Görgens<matthias.goerg...@googlemail.com> wrote: >> It seems to me, that you just need a selection algorithm which works in >> O(n * k) time for k arbitrary elements. If you combine O(n*k) selection >> algorithm with any O(n * lg n) sort, you furfil your time constrain. > > I guess, we also want the list to be sorted in O(1) after having > selected every element. >
I think he's suggesting something along the lines of: for the first \log n requests, use a selection. On the \log n + 1th request, just sort the whole thing. This obviously isn't the spirit of what's wanted, but does in fact meet the time bounds. AHH _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
