2
$\begingroup$

How to find median of k sorted arrays each of length n? Note that total elements would be n*k. I know it can be done in O(n*k*log(k)) using merge technique. I am looking for a better time efficient solution..Like for 2 arrays it can be done in O(log(n)) time..I am trying to use the same logic here but couldn't apply..

$\endgroup$
8
  • 1
    $\begingroup$ Try aiming at a complexity of $O(k\log n)$. $\endgroup$ – Yuval Filmus Feb 4 '18 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$ – Daniel Saad Feb 5 '18 at 0:55
  • 1
    $\begingroup$ @user172818 See geeksforgeeks.org/median-of-two-sorted-arrays $\endgroup$ – Jim Mischel Feb 11 '18 at 21:25
  • 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$ – Yuval Filmus Nov 17 '20 at 14:26
  • 1
    $\begingroup$ In one word: no. $\endgroup$ – Yuval Filmus Nov 18 '20 at 9:00
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$
14
  • $\begingroup$ The trivial lower bound is $\log(nk)$. $\endgroup$ – Yuval Filmus Nov 18 '20 at 10:44
  • $\begingroup$ That's a very different question, since we think of $k$ as small, whereas in this post, $k$ is very large. $\endgroup$ – Yuval Filmus Nov 18 '20 at 11:28
  • $\begingroup$ My algorithm is incomplete, however. $\endgroup$ – Yuval Filmus Nov 19 '20 at 12:18
  • $\begingroup$ I think so. You should be able to tell from the algorithm itself. $\endgroup$ – Yuval Filmus Nov 19 '20 at 12:22
  • 1
    $\begingroup$ I have updated my solution with more details. $\endgroup$ – Yuval Filmus Nov 22 '20 at 12:02

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.