6 Jul
2009
6 Jul
'09
7:42 p.m.
On Mon, Jul 6, 2009 at 4:32 PM, Matthias
Görgens
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