In the linear time selection algorithm which finds the ith smallest element in O(n) time our first step is to divide our unordered set into subsets of 5. Why is the size of the subsets chosen to be 5 and how would the algorithm be affected if I chose a different number. Nothing online describes why this number is the chosen subset size..

  • 3
    $\begingroup$ Why don’t you try redoing the analysis yourself with 5 replaced by an arbitrary odd constant? $\endgroup$ – Yuval Filmus Sep 17 '18 at 15:29
  • $\begingroup$ cs.stackexchange.com/q/87626/755, cs.stackexchange.com/q/87992/755 $\endgroup$ – D.W. Sep 18 '18 at 1:23
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Sep 18 '18 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.