8
$\begingroup$

This question already has an answer here:

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$

marked as duplicate by Tsuyoshi Ito, András Salamon, Kristoffer Arnsfelt Hansen, David Eppstein, Kaveh Dec 31 '14 at 9:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from cs.stackexchange.com Dec 29 '14 at 21:56

This question came from our site for students, researchers and practitioners of computer science.