To find median of k sorted arrays of n elements each in less than O(n*k*log(k))

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..

• Try aiming at a complexity of $O(k\log n)$. Feb 4 '18 at 9:48
• Try a divide-and-conquer approach similar to the Select Algorithm in linear time (CLRS). This would give a $O(nk)$ time. Feb 5 '18 at 0:55
• @user172818 See geeksforgeeks.org/median-of-two-sorted-arrays Feb 11 '18 at 21:25
• 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$. Nov 17 '20 at 14:26
• In one word: no. Nov 18 '20 at 9:00

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))$$.

• The trivial lower bound is $\log(nk)$. Nov 18 '20 at 10:44
• That's a very different question, since we think of $k$ as small, whereas in this post, $k$ is very large. Nov 18 '20 at 11:28
• My algorithm is incomplete, however. Nov 19 '20 at 12:18
• I think so. You should be able to tell from the algorithm itself. Nov 19 '20 at 12:22
• I have updated my solution with more details. Nov 22 '20 at 12:02