Consider an algorithm for deterministic selection(called SELECT) where given an
ID: 3623343 • Letter: C
Question
Consider an algorithm for deterministic selection(called SELECT) where given an Array of n elements we do the follwoing. Divide eleements into n/3 groups of size 3 each. We find the medianelement in each group and call each of those median elements m1, m2,..., mn/3 . We then create a set of medians m={m1, m2,..., mn/3}. We use m*=SELECT(m,n/6) - or the median of the mediasn). We use m* as a pivot element. The rank of m* is at least 1/3 and at most 2/3rds. What is the best upper bound on such an algorithm?
Explanation / Answer
select(L,k)
{
if (L has 6 or few elements)
{
sort L
return the element in the kth position
}
partition L into subsets S[i] of three elements each
(there will be n/3 subsets total).
for (i = 1 to n/3) do
x[i] = select(S[i],3)
m*= select({x[i]}, n/6)
partition L into L1m
if (k <= length(L1))
return select(L1,k)
else if (k > length(L1)+length(L2))
return select(L3,k-length(L1)-length(L2))
else return m
}
The pseudo-code above gives us a number of comparisons that can be found by solving the recurrence
T(n) <= 12n/3 + T(n/3) + T(3n/6)
T(n) <= 4n + T(n/3) + T(n/2)
= 4n + cn/3 + cn/2
= n (4 + 5c/6)
If this is to be at most cn, so that the induction proof goes through, we need it to be true that
n (4 + 5c/6) <= cn
4 + 5c/6 <= c
4 <= c/6
c <= 24
proved that we can have induction that T(n) <= 24n (or any larger constant times n).