Share
Explore BrainMass

Medians and Order statistics

Please review problem and verify the solution.

problem
---------
In the algorithm SELECT, the input elements are divided into groups of 5. Will the algorithm work in linear time if they are divided into groups of 7? Argue that SELECT does not run in linear time if groups of 3 are used.

solution
---------
Use groups of k for the analysis. The worst case SELECT will be called recursively on at most n - (n/4 - k) = 3n/4 + k elements.

The recurrence is T(n) <= T(ceiling(n/k)) + T(3n/4 + k) + O(n)
Solve the recurrence by substitution

I believe the solution is the following:
T(n) <= T(ceiling(n/k)) + T(3n/4 + k) + O(n)
<= c(n/k + 1) + 3cn/k + c(k+1) + O(n)
<= cn(1/k + 3/4) + c(k + 1) + O(n) [ this only holds for k > 4 so we have proved it works for any group size of 4 or more]
<= cn

Solution Summary

Medians and Order statistics are evaluated.

$2.19