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?


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.