Chapter 9, Problem 3P

(a)

Program Plan Intro

To describe an algorithm that uses $Ui(n)$ comparisons to find the i^th smallest of n -elements where $Ui(n)=\{\begin{array}{l}T(n)\\ \lfloor n/2\rfloor +Ui(n/2)+T(2i)\end{array}\begin{array}{l}i\ge n/2\\ otherwise\end{array}\}$ .

(b)

Program Plan Intro

To show that $Ui(n)=n+O(T(2i)\lg (n/i))$ if $i<n/2$ .

(c)

Program Plan Intro

To show that $Ui(n)=n+O(\lg n)$ if i is a constant less than $n/2$ .

(d)

Program Plan Intro

To show that $Ui(n)=n+O(T(2n/k)\lg k)$ if $i=n/k$ for $k\ge 2$ .