- #1

- 15

- 0

## 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[tex]\bigcup[/tex] X2 [tex]\bigcup[/tex] ... [tex]\bigcup[/tex] Xn efficiently.

(n * log(n), n^2 is not acceptable, also no probabilistic, expected runtime)

Also, Xi [tex]\bigcap[/tex] Xj = [tex]\phi[/tex] [tex]\forall[/tex] i, j s.t. i[tex]\neq[/tex]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)

Last edited: