In chapter 10.3. Selection in worst - case linear time ($k$th minimum) from Introduction to Algorithms by Cormen, Leiserson and Rivest, the time complexity expected for step 5 of the algorithm presented in this chapter is said to take $T(n)=7n/10 + 6$ at worst.

From my point of view the time complexity is the one specified above because the number of elements larger than the median of all medians is at least $3n/10-6$, thus the remaining search space is $7n/10 + 6$, where $n$ is the size of input data.

How off am I?

  • 1
    $\begingroup$ I am confused by your question. Are you disagreeing or agreeing with the claim? Where/why do you think you're "off"? $\endgroup$ – ryan Oct 27 '17 at 22:17
  • $\begingroup$ @ryan I agree with the claim and I'm trying to give myself some kind of intuitive reasoning. I'm not entirely sure that my way of seeing this is plausible/ true. $\endgroup$ – theSongbird Oct 28 '17 at 7:52
  • $\begingroup$ Note that you are in all likelihood linking to a pirated copy of CLRS. (I doubt that the owner of the website has a license for world-wide distribution of CLRS.) You should instead transcribe the algorithm here so the question can stand on its own. $\endgroup$ – Raphael Oct 29 '17 at 11:33
  • $\begingroup$ Which reasoning does the book give? Have you tried a precise derivation as opposed to remaining on the intuitive level? $\endgroup$ – Raphael Oct 29 '17 at 11:34

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.