Just the One of the Few (jtootf) wrote in algorithms,
Just the One of the Few
jtootf
algorithms

n-th order statistics of the immutable data

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
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 14 comments