Date: 03/04/09 (Algorithms)    Keywords: no keywords

what's the best asymptotic time complexity for a n-th order statistics algorithm on the immutable array of size N with memory consumption less then or equal to O(log N)? median of medians algorithm gives O(N) time complexity in the worst case, but I'm not sure about it's memory boundaries for the r/o array

UPD: anyway, it would be much interesting too for the case of the memory consumption less then or equal to O(sqrt N); or even O(K * N) where 0 < K << 1

Source: http://algorithms.livejournal.com/101906.html