$7.$ For n distinct elements with positive weights x$1,$ x$2,...,$ xn with positive weights w$1,$ w$2,...,$ wn such that

i$=1$nwi$=1$ the weighted lower median is the element xk such that

xixk wi $12$

Observe that the median of x$1,$ x$2,...,$ xn is the weighted median for wi $=1$n for i $=1,2,...,$ n$.$

$($a$)$ Show how to compute the weighted median of n elements in O$($n log n$)$ worst case time using sorting. You do not need to write pseudo$-$code, simply explain your approach and justify the claim for its complexity.

$($b$)$ Show how to compute the weighted median in O$($n$)$ time using the Select algorithm discussed in class.