Assuming that you can find the median of a 6-element list in B steps and that th
ID: 3726367 • Letter: A
Question
Assuming that you can find the median of a 6-element list in B steps and that this is defined as returning the 3rd smallest value: (a) Determine the of the worst-case runtime of the "Median of Medians" algorithm assuming it uses "6" rather than "3" or "5" as we had seen in class. This means that you look at the recurrence always assuming the biggest possible bucket in which to recurse. Show your work. (b) Once you have that asymptotic class, use constructive induction to construct the best Big-O constant C that you can for that high-order term. If B is a part of that constant, keep the B in the final answer. Again, show your work. REMINDER: To make the algebra nicer, and to reflect that you might need to compare the pivot to itself when you do the partitioning to make the code easier, you should say that partitioning has a cost of exactly n rather than n-1.
Explanation / Answer
(A)
If the 'Median of Median' uses a bucket of 6 then the size of the median list will be 16.6% of the total list and the other recursive call recurse maximum on 80% of the list. Hence, the resulting recursion will be:
T(n) >= T(n/6) + T(5*n/6) + O(n)
>= T(n/36) + T(5*n/36) + 2*O(n)
>= ...
>= T(1) + T(5) + O(n*log6 n) (Equation 1)
Hence the running time of the algorithm is (n*logn)
(B)
Here, T(n) >= c*(n*log6n)
Now it requires B steps to solve a list of 6 elements.
Therefore, T(1) = B
From (1)
T(n) = T(1) + T(5) + O(n*log6 n)
T(n) = B+5*B + O(n*log6 n)
Hence, the constant is 6*B.