1

I have found some questions similar to this on the site but they do not give a deterministic solution , like the median of median approach which is only gives an approximate albeit low error value of the median.

Thus I am looking for a 'black box' algorithm that is complete in itself and is deterministic as an answer.

N.S.JOHN
  • 111
  • 4
  • No, if you need the correct answer, you can't do it in linear time, if you need linear time an approximation is the best you can get. – derpirscher Mar 08 '22 at 08:32
  • There is [quickselect](https://en.wikipedia.org/wiki/Quickselect), which is Θ(n) on average, but Θ(n²) in the worst-case. – Stef Mar 08 '22 at 10:04

0 Answers0