<p>You are given <span class="math-container">$k$</span> sorted arrays <span class="math-container">$A_1, A_2, ..., A_k$</span>, each containing <span class="math-container">$n$</span> elements.</p>
<blockquote>
<p><strong>How fast can you compute the median of <span class="math-container">$A_1 \cup A_2 \cup ... \cup A_k$</span> ?</strong></p>
</blockquote>
<hr />
<p>I have a solution running in <span class="math-container">$\Theta(k\log k\log n)$</span>, but this seems rather inefficient if <span class="math-container">$k=\Omega(2^\frac{n}{\log n})$</span>, as we can always ignore the order, think of it as a unsorted array of <span class="math-container">$nk$</span> elements, and solve it in <span class="math-container">$O(nk)$</span> time.</p>
<blockquote>
<p>Assuming <span class="math-container">$k=\omega(1)$</span> (hence the fact the arrays are sorted give us some information), is there a sub-linear median finding algorithm (regardless of the ratio between <span class="math-container">$k$</span> and <span class="math-container">$n$</span>)?</p>
<p>Assuming <span class="math-container">$k=\text{poly}( n)$</span>, can we beat <span class="math-container">$O(k\log k\log n)$</span>?</p>
<p><strong>Can we prove a lower bound for the problem (maybe <span class="math-container">$\Omega(k\log n)$</span>?)?</strong></p>
</blockquote>

CC BY-SA 3.0
2014-12-28T21:49:12.143Z
Perhaps you would like to ask that on cstheory.
Yuval Filmus
CC BY-SA 3.0
2014-12-29T21:56:40.473Z
Although this question is on-topic on [cs.se], I am migrating it to [cstheory.se] at the asker's request.
Gilles 'SO- stop being evil'
CC BY-SA 3.0
2014-12-30T02:13:28.577Z
See [this question](http://cstheory.stackexchange.com/questions/20944/select-in-union-of-sorted-arrays-already-known/).
Chao Xu
<ds.algorithms><time-complexity>
Finding a median in a union of sets given as sorted arrays
R B
# Finding a median in a union of sets given as sorted arrays

(Asked by: username_0 on 2014-12-28)

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)$?)?**

**Tags:** ds.algorithms, time-complexity
> **Comments:**
> **username_1**: Perhaps you would like to ask that on cstheory.  
> **username_2**: Although this question is on-topic on [cs.se], I am migrating it to [cstheory.se] at the asker's request.  
> **username_3**: See [this question](http://cstheory.stackexchange.com/questions/20944/select-in-union-of-sorted-arrays-already-known/).  

---

## 0 answers

