8
$\begingroup$

You are given $k$ sorted arrays $A_1, A_2, ..., A_k$, each containing $n$ elements.

How fast can you compute the median of $A_1 \cup A_2 \cup ... \cup A_k$ ?


I have a solution running in $\Theta(k\log k\log n)$, but this seems rather inefficient if $k=\Omega(2^\frac{n}{\log n})$, as we can always ignore the order, think of it as a unsorted array of $nk$ elements, and solve it in $O(nk)$ time.

Assuming $k=\omega(1)$ (hence the fact the arrays are sorted give us some information), is there a sub-linear median finding algorithm (regardless of the ratio between $k$ and $n$)?

Assuming $k=\text{poly}( n)$, can we beat $O(k\log k\log n)$?

Can we prove a lower bound for the problem (maybe $\Omega(k\log n)$?)?

$\endgroup$