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:

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:

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

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

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