2
$\begingroup$

How do I efficiently find the median of $k$ sorted arrays each of length $n$? Note that the total number of elements will be $nk$. I know it can be done in $O(nk \log k)$ time using merge technique. Is there a more efficient algorithm?

For two arrays it can be done in $O(\log n)$ time, but I can't see how to apply that here.

$\endgroup$
3
  • 1
    $\begingroup$ Try aiming at a complexity of $O(k\log n)$. $\endgroup$ Feb 4, 2018 at 9:48
  • $\begingroup$ Try a divide-and-conquer approach similar to the Select Algorithm in linear time (CLRS). This would give a $O(nk)$ time. $\endgroup$ Feb 5, 2018 at 0:55
  • 1
    $\begingroup$ Since $x/\log x$ is increasing (for $x >e$) and $k \leq n$, we have that $k/\log k \leq n/\log n$, and so $k\log n \leq n\log k$. $\endgroup$ Nov 17, 2020 at 14:26

1 Answer 1

5
$\begingroup$

Let us denote the arrays by $A_1,\ldots,A_k$, their sizes by $|A_1|,\ldots,|A_k|$, their medians by $m_1,\ldots,m_k$, and their union by $\mathbf{A}$. We will try to solve the following more general problem: given $t$, determine the $t$'th smallest element in $\mathbf{A}$.

Let $m_r = \min(m_1,\ldots,m_k)$ and $m_s = \max(m_1,\ldots,m_k)$. Define $$ N = \sum_{i=1}^k \lceil |A_i|/2 \rceil. $$ There are at least $N$ many elements in $\mathbf{A}$ whose value is at least $m_r$, and at least $N$ many elements in $\mathbf{A}$ whose value is at most $m_s$.

If $N \geq t$ then elements larger than $m_s$ cannot be the $t$'th smallest element. In particular, we can throw out the upper half of $A_s$. Similarly, if $N \geq n+1-t$ then elements smaller than $m_r$ cannot be the $t$'th smallest element, and so we can throw out the lower half of $A_r$ (and update $t$ accordingly, by subtracting $\lfloor |A_r|/2 \rfloor$). Note that $\min(t,n+1-t) \leq \lceil n/2 \rceil \leq N$, and so at least one of these cases must happen.

How many rounds does it take this algorithm to complete? Each round results in reducing the size of one of the $k$ arrays roughly by half (the reduction is $\ell \mapsto \lceil \ell/2 \rceil$). One can check that it takes $\lceil \log \ell \rceil$ steps to reduce each array to a singleton. Therefore the number of rounds it takes the algorithm to narrow down all arrays to a single element is $$ \sum_{i=1}^k \lceil \log |A_i| \rceil \leq k + \sum_{i=1}^k \log |A_i| \leq k + k \log \sqrt[k]{|A_1| \cdots |A_k|} \leq k + k \log \frac{|\mathbf{A}|}{k}. $$ After an initial round which takes $O(k\log k)$ time, each subsequent round can be implemented in $O(\log k)$, if we store the medians in an appropriate data structure such as a heap. Following this phase, we are left with $k$ elements, and we can run a linear time selection algorithm to find the $t$'th smallest element in $O(k)$. In total, this algorithm runs in time $$ O\bigl(k\log k + k \log \tfrac{|\mathbf{A}|}{k}\bigr) = O(k\log |\mathbf{A}|). $$ When $|A_i|=n$ for all $i$, this is $O(k\log (kn))$.

$\endgroup$
4
  • $\begingroup$ The trivial lower bound is $\log(nk)$. $\endgroup$ Nov 18, 2020 at 10:44
  • $\begingroup$ The algorithm finds the $t$’th smallest element. The parameter $t$ is updated as we go. $\endgroup$ Nov 23, 2020 at 6:03
  • $\begingroup$ This answer works for arrays of any size. They need not have identical sizes. $\endgroup$ Jan 18, 2021 at 7:35
  • $\begingroup$ The notation $|A_i|$ stands for the length of the array $A_i$. $\endgroup$ Jan 18, 2021 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.