Finding median in theta(n^lg3) time
Dear all,
I'm a bit stuck on my algorithm exercise, the problem asks us to construct an algorithm that finds the median of an array in theta(n^lg3) time. According the the Master Theorem
the recurrence relation of this algorithm should look like the following:
T(n) = / theta(1)n =1
\ 3T(n/2) + theta(n)
I have spent hours trying to derive an algorithm out of the above relation, but still stuck,
any hint would be appreciated!!
Thanks
[488 byte] By [
sdpa] at [2007-10-3 7:14:29]
The answer was obvious, even though I've never come across this inefficient [1] algorithm before, but I'll try to explain the steps I probably did subconsciously. Note that I'm assuming unique elements because it simplifies the analysis. Feel free to make it more rigorous.
You deduce that you're going to want to do 3 recursive calls per iteration. The obvious question is on which sublists. Since a priori you have no useful information, the first division is probably into arbitrary halves. That accounts for two recursive calls: whence the third? Clearly you have to combine the results in some way.
Let the list be L, the two halves be L1 and L2, and their medians be m1 and m2. Without loss of generality, let m1 < m2. Then you know that a half of L1 (and hence a quarter of L) is less than m1, and a half of L (the top halves of L1 and L2) is greater than m1. Similarly a quarter of L is greater than m2 and a half of L is less than m2. That should be enough of a hint for you to make progress.
[1] Finding the median can be done in O(n) time.
