### solving the selection problem given the im/n smallest element

Sat 10 December 2011

Given a black-box capable of finding the $$\left \lfloor \frac{in}{m} \right \rfloor$$ smallest element in an array of length $$n$$, where $$1 \leq i \lt m$$ are constant, find the $$k$$-th smallest element in a given array using the black-box in linear time.

Suppose our black-box is capable of finding the median of an array of length $$n$$, how would we solve the same problem?

1. Find the median of $$A[p..r]$$ using the black-box.
2. Partition $$A$$ using the median as our pivot. Suppose the median's index after partitioning is $$q$$.
3. If $$q-p+1 = k$$ then $$A[q]$$ is the element we're looking for and we're done.
4. If $$k \lt q-p+1$$, recursively call our procedure on $$A[p..q-1]$$, otherwise call it on $$A[q+1..r]$$ with $$k=k-(q-p+1)$$.

Steps 1 and 2 take $$\Theta(n)$$ time. In step 4 we cut the array in half, so we can express the running time of our algorithm using this recurrence relation:

$$T(n)=T\left (\frac{n}{2} \right )+\Theta(n)$$

Solving this gives us $$T(n)=\Theta(n)$$.

Back to our original problem: if we use the exact same algorithm, except in step 1 find the $$\left \lfloor \frac{in}{m} \right \rfloor$$ smallest element in $$A[p..q]$$ where $$q-p+1=n$$, it will still work.

The question that remains, is it still linear? It turns out the answer is yes. Let's prove it:

$$T(n)=T(\max (\left \lfloor \frac{in}{m} \right \rfloor-1, n-\left \lfloor \frac{in}{m} \right \rfloor-1))+\Theta(n)$$

Let $$an \in \Theta(n)$$. Suppose there exists some $$c$$ such that $$T(n) \leq cn$$, then:

\begin{align} T(n) & =T(\max (\left \lfloor \frac{in}{m} \right \rfloor-1, n-\left \lfloor \frac{in}{m} \right \rfloor-1))+an \\\\\\ & \leq c (\max (\left \lfloor \frac{in}{m} \right \rfloor-1, n-\left \lfloor \frac{in}{m} \right \rfloor-1))+an \\\\\\ &\leq c (\max ( \frac{in}{m} , n- \frac{in}{m} ))+an \\\\\\ &=cn(\max ( \frac{i}{m} , 1-\frac{i}{m} ))+an \end{align}

Since $$\frac{i}{m} \lt 1$$, let us denote $$q=\max ( \frac{i}{m} , 1-\frac{i}{m} ) \lt 1$$:

$$T(n) \leq cqn+an = cn - (1-q)cn+an = cn+(an-(1-q)cn)$$

We are looking for $$c$$ such that $$an-(1-q)cn \leq 0$$, any $$c \geq \frac{a}{1-q}$$ will do.