Introduction to Algorithm,3rd

9.3 Selection in worst-case linear time

I have a question about its proof.

enter image description here

I have selected that sentence.

enter image description here

I agree that the number of elements larger than x is

$$ 3\times(\lceil\frac{1}{2}\times \lceil\frac{n}{5}\rceil \rceil -2) $$

but, I think the number of elements less than x is at least $3\times(\lceil\frac{1}{2}\times \lceil\frac{n}{5}\rceil \rceil)-1$

Am I right? Since the left up side contains $\lceil\frac{1}{2}\times\lceil\frac{n}{5}\rceil\rceil$ groups. Each contribute 3 elements except x itself.

Besides, step5 is

If i = k, then return x. Otherwise, use SELECT recursively to find the i-th smallest element on the low side if i < k, or the (i - k)-th smallest element on the high side if i > k.

How can we get

$$ \frac{7n}{10} + 6 $$ in step 5?

  • $\begingroup$ I know the second problem, that is n-(3n/10-6) $\endgroup$ – skytree Apr 7 '17 at 19:37
  • $\begingroup$ It's symmetrical, so shouldn't the reasoning be the same for 'number of elements larger than x' and 'number of elements smaller than x'? Why would you expect to get a different lower bound for those two quantities? I apologize if I'm missing something. Oh, and welcome to the site! $\endgroup$ – D.W. Apr 7 '17 at 21:53
  • $\begingroup$ @D.W. Thank you. I count in that figure and find that it's $3\times(\lceil\frac{1}{2}\times \lceil\frac{n}{5}\rceil \rceil)-1$. I have a [link, page 26 below](ocw.mit.edu/courses/electrical-engineering-and-computer-science/… ) to mit algorithm Fall 2005, it is different from the book. $\endgroup$ – skytree Apr 7 '17 at 22:58

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.