Selection algorithm SELECT for finding the (i^{\rm th}) smallest element:

  1. Divide the array into (\lfloor n/5\rfloor) groups of 5 elements each (last one has (n\mod 5)). (O(n))

  2. Find the median of each of the groups by insertion-sorting the elements of each group and picking the median from the sorted list of group elements. (O(n))

  3. Use SELECT recursively to find the median (x) of the (\lceil n/5\rceil) medians found. (T(\lceil n/5\rceil))

  4. Partition the array into (L) & (R) based on (x). Let (k=\vert L\vert + 1). Note that (x) is (k^{\rm th}) smallest element and there are (n-k) elements in (R). (O(n))
  5. Based on (i):
    1. (i=k), return (x).
    2. (i<k), recurse SELECT on (L) for (i)
    3. (i>k), recurse SELECT on R for (i-k)

We see that atleast (1/2) of the medians found in 2 are greater than or equal to medians-of-medians (x). Thus atleast half of the (\lceil n/5\rceil) groups contribute atleast 3 elements that are greater than (x), except for the last one and the group containing (x) itself.Thus number of elements greater than (x) is at least:

(\displaystyle 3\left(\left\lceil\frac 12\left\lceil\frac n5\right\rceil\right\rceil-2\right)\ge \frac {3n}{10}-6)

Thus in worst case step 5 calls SELECT recursively on atmost (7n/10+6) elements. \(\begin{align} T(n)&\le cn+T(n/5)+T(7n/10)\\ &\le cn + \left(c\frac n5+T(n/5^2)+T(7n/50)\right)+\left(c\frac {7n}{10}+T(7n/50)+T(7^2n/10^2)\right)\\ &= cn + 9\frac {cn}{10} + T(n/5^2) + 2T(7n/50) + T(7^2n/10^2)\\ &\le \ldots\\ &\le \sum_{i=0^h}\left(\frac {9}{10}\right)^icn+\ldots\\ &\le cn\frac 1{1-9/10} = O(n) \end{align}\)

Max height of tree is ((7/10)^h\le 1\implies h\ge \log_{10/7}n).