I was analyzing Randomized Quick Selects' time complexity, as a function of n - the size of the input, and k - the index of the element that needs to be selected.
The time complexity dependence on n was linear as was expected, but the dependence on k was of an inverted parabola - i.e the time complexity was highest when trying to select the median and lowest when trying to select the first or last element of the array.

Is there an explanation for that?

  • 1
    $\begingroup$ Have you seen this? 11011110.github.io/blog/2007/10/09/blum-style-analysis-of.html $\endgroup$ – Yuval Filmus Jun 10 '19 at 14:44
  • $\begingroup$ Let me add to the link that the expected number of comparisons is $(1+o(1))2n(1 + h(k/n))$, where $h$ is the (natural) entropy function. I imagine that this formula can be interpreted in some information-theoretic way. $\endgroup$ – Yuval Filmus Jun 11 '19 at 16:41

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.