On Mon, Jul 6, 2009 at 4:32 PM, Matthias
Görgens<
matthias.goergens@...> 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@...
http://www.haskell.org/mailman/listinfo/haskell-cafe
