# proof of selection in worst-case linear time

Introduction to Algorithm,3rd

9.3 Selection in worst-case linear time

I have a question about its proof.

I have selected that sentence.

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?

• I know the second problem, that is n-(3n/10-6) – skytree Apr 7 '17 at 19:37
• 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! – D.W. Apr 7 '17 at 21:53
• @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. – skytree Apr 7 '17 at 22:58