0

I need to use the selection algorithm (with the median of medians version of it), but the space complexity of it is too high for me. Is there a way to reduce the space complexity to Ņē(1)? Thanks.

beaker
  • 16,331
  • 3
  • 32
  • 49
Tal
  • 11
  • 1
  • Do you want to find k-th order statistic? – Yola Dec 09 '17 at 17:11
  • How about quick select? https://en.wikipedia.org/wiki/Quickselect It's constant space if you're able to re-order the input array. Otherwise it needs a copy to work on. – Gene Dec 09 '17 at 17:47
  • See https://stackoverflow.com/questions/34562256/why-is-the-median-of-medians-algorithm-described-as-using-o1-auxiliary-space , and specifically, the paper pointed out by @Stefan Pochmann – Zvika Dec 10 '17 at 19:37

0 Answers0