Find the median of a set of sorted lists, Computer Science

[chy1013m1]

Homework Statement

Given a set of sorted lists {X1, X2, ..., Xn} each Xi is in R^n , devise a divide and conquer algo that
finds the median of X1$$\bigcup$$ X2 $$\bigcup$$ ... $$\bigcup$$ Xn efficiently.
(n * log(n), n^2 is not acceptable, also no probabilistic, expected runtime)
Also, Xi $$\bigcap$$ Xj = $$\phi$$ $$\forall$$ i, j s.t. i$$\neq$$j

Homework Equations

already know a procedure that finds the median of 2 equal sized, sorted lists in O(log(n)) time

The Attempt at a Solution

- sort the lists by its median values, re-label them to be X1, X2..., Xn
- divide the lists into L = {X1, ..., X[floor(n/2)]} and U = {X_ceil(n/2) ... , Xn}
- find the med points of L, call it "ml", and the med point of U, call it "mu"
- remove elements < ml from L, elements > mu from U, get new set of L', and U'.
but at this point, the lists could be no equal in size, if we do a merge it could blow up the runtime,
since merge is theta(n)

 

[basePARTICLE]

X is list ; M is median ; r is # of elements less than M.
X1 : (M1,r1)
X2 : (M2,r2)
X3 : (M3,r3)
..
Xn : (Mn,rn)

^
larger r's
r
r x x
r x x xx x
r x x x xx x x
r xxx xxx xx x x x
r xxx xxx xxxxxx x
m_m_m_m_m_mm___m___> larger medians

can you notice anything about that data?

 

[piercas]

and we have to do it n times.

To avoid this, we can use the following algorithm:

1. Initialize L' and U' as empty lists.
2. For each list Xi in L, add the element at index floor(n/2) to L'.
3. For each list Xi in U, add the element at index ceil(n/2) to U'.
4. Find the median of L' and U' using the known algorithm for finding median of two equal sized, sorted lists.
5. If the median of L' is less than the median of U', then the median of the original set of lists is in the upper half of L and the lower half of U.
6. If the median of L' is greater than the median of U', then the median of the original set of lists is in the upper half of U and the lower half of L.
7. Repeat steps 2-6 until the median of the original set of lists is found.

This algorithm has a runtime of O(nlog(n)) since each step involves finding the median of two equal sized, sorted lists which takes O(log(n)) time, and there are n lists in total. Therefore, this algorithm satisfies the given constraints of O(nlog(n)) runtime and no probabilistic or expected runtime.