3 ms·

According to the man himself, this algorithm was found by Manuel Blum when trying to prove that it was impossible to do k selection in linear time deterministic

According to the man himself, this algorithm was found by Manuel Blum when trying to prove that it was impossible to do k selection in linear time deterministically

svantana 13y ago
Do you know if that's been proven, or is it still an open question?
- awoolf27 13y ago
  The algorithm described in the article is deterministic and linear time -- exactly what Blum was trying to disprove as possible