SELECT with groups of 3

Exercise 9.3-1 asks you to show that the $SELECT$ algorithm still runs in linear time if the elements are divided into groups of 7. This problem asks about dividing into groups of 3.

• Show that $SELECT$ runs in linear time if you divide the elements into groups whose size is any odd constant greater than 3.
• Show that $SELECT$ runs in $O(n\; lg\; n)$ time if you divide the elements into groups of size 3

Because the bound in part (b) is just an upper bound, we do not know whether the groups-of-3 strategy actually runs in $O(n)$ time. But by repeating the groups-of-3 idea on the middle groups of medians, we can pick a pivot that guarantees $O(n)$ time. The $SELECT3$ algorithm on the next page determines the $i^{\;th}$ smallest of an input array of $n \gt 1$ distinct elements.

• Describe in English how the $SELECT3$ algorithm works.Include in your description one or more suitable diagrams.
• Show that $SELECT3$ runs in $O(n)$ time in the worst case. [1]

 

The worst-case linear-time median-finding algorithm was devised by Blum, Floyd, Pratt, Rivest and Tarjan [2]. This exercise improves the original algorithm [2] to use groups of 3 without deteriorating its performance. The constant factors of this new algorithm $SELECT3$ outperforms that of its counterpart $SELECT$. Therefore, it pays to understand the relative merits of $SELECT3$. What follows is the $SELECT3$ algorithm.

$SELECT3(A, p, r, i)$  

    $\phantom{{}++{}}$ `while` $(r - p + 1)\; mod\; 9 \neq 0$  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$  `for` $j = p + 1$ to $r$  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $A[p] \gt A[j]$  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ exchange $A[p]$ with $A[j]$  

    $\phantom{{}++{}}$ `if` $i == 1$  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$ `return` $A[p]$  

    $\phantom{{}++{}}$ $p = p + 1$  

    $\phantom{{}++{}}$ $i = i - 1$  

    $\phantom{{}++{}}$ $g = \frac{(r - p + 1)}{3}$  

    $\phantom{{}++{}}$  `for` $j = p$ to $p + g - 1$  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$ sort $\langle A[j],\; A[j + g],\; A[j + 2g]\rangle$  in place  

    $\phantom{{}++{}}$ $g^\prime = \frac{g}{3}$  

    $\phantom{{}++{}}$ `for` $j = p + g$ to $p + g + g^\prime - 1$  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$ sort $\langle A[j],\; A[j + g^\prime],\; A[j + 2g^\prime]\rangle$  in place  

    $\phantom{{}++{}}$ $x = SELECT3(A, p + 4g^\prime, p + 5g^\prime - 1, \lceil \frac{g^\prime}{2} \rceil)$  

    $\phantom{{}++{}}$ $q = PARTITION-AROUND(A, p, r, x)$  

    $\phantom{{}++{}}$ $k = q - p + 1$    

    $\phantom{{}++{}}$ `if` $i == k$  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$ `return` $A[q]$  

    $\phantom{{}++{}}$ `elseif` $i < k$  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$  `return` $SELECT3(A, p, q - 1, i)$  

    $\phantom{{}++{}}$ `else` `return` $SELECT3(A, q + 1, r, i - k)$   

What follows are our answers to the problem.

• Let $k$ be the group size and $n$ be the number of elements. 
  Number of groups $g = \frac{n}{k}$ for some odd constant $k$
  Number of elements $\lt$ pivot (or $\gt$ pivot) $\ge \lceil \frac{g}{2}\rceil \times \lceil \frac{k}{2}\rceil = \lceil\frac{\frac{n}{k}}{2}\rceil \times \lceil \frac{k}{2}\rceil$
  Number of elements in low or high side of the partition around x $\ge \frac{n}{2k} \times \frac{k}{2} = \frac{n}{4}$
  Number of elements in play after partition around x $\le n - \frac{n}{4} = \frac{3n}{4}$
  $T(n) \le T(\frac{n}{k}) + T(\frac{3n}{4}) + \Theta(n)$.
  This runs in $\Theta(n)$ time if and only if: $\frac{n}{k} + \frac{3n}{4} \lt n$.
  And this holds for any odd constant $k \gt 4$, thus, proving our claim.

• For groups of size $3$,
  number of 3 element groups $= g = \frac{n}{3}$, where n denotes the total number of elements in the input array.
  Number of group medians in the blue region $= \lceil \frac{g}{2} \rceil$
  For each group median, one additional element is less than it.
  So, the number of elements in the blue region $\ge \lceil \frac{g}{2} \rceil \times 2 \ge \frac{g}{2} \times 2 = g$
  Thus, total number of elements in play after partition around $x \le n - g = n - \frac{n}{3} = \frac{2n}{3}$   
  What follows is our recurrence for groups of size 3 elements:  $T(n) \le T(\frac{n}{3})\; +\; T(\frac{2n}{3}) + \Theta(n)$
  We will show that, $T(n) = O(n\; log\;n)$ by substitution.
  We'll prove that  $T(n) \le c \cdot n\; \cdot log\;n$ for suitably large constant $c \gt 0$ and all $n \gt 0$
  $T(n) \le c \cdot \frac{n}{3} \cdot log(\frac{n}{3}) + c \cdot \frac{2n}{3} \cdot log(\frac{2n}{3}) + \Theta(n)$
  $T(n) \lt c \cdot \frac{n}{3} \cdot log(n) + c \cdot \frac{2n}{3} \cdot log(n) + \Theta(n)$   
  $T(n) \lt c \cdot n \cdot log(n) + \Theta(n)$
  $T(n) = O(n \; log\; n).$
  Thus, running time of $SELECT$ for groups of 3 elements is: $O(n \cdot log\; n)$

• In the while loop, from lines 1 to 10, in each iteration we keep the smallest element in A[p], and then find the (i - 1)st smallest element in the subarray A[p + 1: r]. We do it < 9 iterations. The while loop terminates when we have the remaining number of elements which is divisible by 9. Then, we divide these remaining elements into groups of 3 elements each, and sort them in place. Now, all group medians lie in the middle third of A[p:r]. Then, we take the group medians (middle third), and further divide them into 3 element subgroups, sorting them in place as before. All subgroup medians now lie in the middle 9th of A[p:r]. Then we find the pivot x as the median of subgroup medians recursively. The rest is trivial, thus it is not described here. Please see the figure for more details.

• Number of elements $\lt x$ (or $\gt x$) $= \lceil \frac{g}{2} \rceil \times 2 \ge g = \frac{n}{3}$
  Number of elements in the blue region $\ge \frac{n}{3}$
  Thus, total number of elements in play after partition around $x \le n - \frac{n}{3} = \frac{2n}{3}$ 
  The recurrence is therefore given by $T(n) \le T(\frac{n}{9})\; +\; T(\frac{2n}{3})\; +\; \Theta(n)$ 
  Our inductive hypothesis is: $T(n) \le cn$ for some suitably large constant $c \gt 0$ and for all $n \gt 0$ 
  Substituting this in to the right hand side of the recurrence, we then obtain: $T(n) \le \frac{cn}{9} \; +\; \frac{2cn}{3}\; + \Theta(n)$ 
  $T(n) \le \frac{7cn}{9} \;+\; \Theta(n)$ 
  $T(n) \le cn - \frac{2cn}{9} \;+\; \Theta(n)$ 
  $T(n) \le cn$ 
  and this holds if c is chosen large enough that $\frac{2c}{9}$ constant dominates the upper bound constant hidden by the term $\Theta(n)$, thus proving our claim. 
  Thus $SELECT3$ runs in $O(n)$ time in the worst case. 

References

[1] https://www.amazon.com/Introduction-Algorithms-fourth-Thomas-Cormen/dp/026204630X

[2] http://i.stanford.edu/pub/cstr/reports/cs/tr/73/349/CS-TR-73-349.pdf