2
$\begingroup$

I think about following problem:
There are given three sorted arrays $A,B,C$ (each of them is length $n$).
Every array has distinct elements. Find median of union $A,B,C$.

I consider following approach:
Let's consider $A_i, B_i, C_i$, where $i=n/2$. There are six cases - but I consider only one (rest of them is analogous). Let $A_i\le B_i\le C_i$: Now we may dispse $1/3$ elements - $A[1...n/2]$ and $C[n/2 + 1... n]$.
Unfortunately I can't estimate time of run this algorithm.
I should solve recusrion equality: $T(n) = T(2/3n) + 1$
$(T(0) = T(1) = 1$, but I can't.

I am thinking about better algorithm. Can you suggest something ?

Edit
I am goint to say more about this algorithm. The key idea is using Divide and conquer method. In each step we may dispose $\frac{1}{3}$ elements. Lets $i = n/2$. Let suppose that $A_i \le B_i \le C_i$ (rest of cases is analogous). Look at example:
enter image description here

In every case I dispose $1/3$ elements and get smaller problem.

$\endgroup$
  • $\begingroup$ Our reference question gives some techniques that should let you solve the recurrence relation you give and determine how good your algorithm is. (Hint: it's very good.) $\endgroup$ – D.W. Oct 5 '15 at 0:50
1
$\begingroup$

The recurrence relation can be solved as follows: for large $n$,

$$T(n) = T\left(\frac{2}{3}n\right) + 1 = T\left(\frac{2^{2}}{3^{2}}n\right) + 2 = \cdots = T\left(\left(\frac{2}{3}\right)^kn\right)+k$$

This iterative process ends when a $T(m)$ is called with $m \leq 1$. Now for what $k$ do we have $\frac{2^{k}}{3^{k}}n \leq 1$? It is $ ^{\frac{3}{2}}log(n)$. (verify this for yourself)

A good way to do this is using an insight from the $\texttt{MergeSort}$ algorithm. It sorts an algorithm by consequtively merging increasingly long sorted substrings. Here's how it goes: you keep three indices, say $i,j,k$, which start at $0$. You iterate them over the three arrays, each time incrementing the index which points to the highest value of its respective array, until you've encountered half of all elements, i.e. $i+j+k=\frac{3n}{2}$. When that has happened, you have encountered the median. Here's this algorithm as pseudocode:

$\texttt{TernaryMedian}(\texttt{array } A, \texttt{array } B, \texttt{array } C):$

int $i, j, k :=0$

while $i+j+k < \frac{3n}{2}$ do

$\quad$ if $A_i > B_j$ then

$\quad\quad$ if $A_i > C_k$ then $i := i + 1$

$\quad\quad$ else $k := k + 1$

$\quad$ else if $B_j > C_k$ then $j := j + 1$

$\quad$ else $k := k + 1$

end while

$median := max(A_i, B_j, C_k)$

This algorithm runs in time $O(n)$ and makes $3n$ comparisons in the best case and $\frac{9}{2}n$ comparisons in the worst; I'll leave the average case to you. This algorithm can be improved if you keep a pointer to the array containing the highest value of any of the pointers but which was not the subject of last iteration's increment. I'll leave it up to you to figure out why. Then you get $\frac{3}{2}n+1$ comparisons in the best case and $3n$ comparisons in the worst.

It may help to first look up $\texttt{MergeSort}$ on Wikipedia for merging two substrings, and then think about how you would merge three substrings. Hope this helps.

$\endgroup$
  • $\begingroup$ This is a very nicely written up answer, with a good explanation of the intuition and the details. One comment: It should be possible to do much better than $O(n)$ time. In fact, the algorithm in the question already achieves $O(\log n)$ time. $\endgroup$ – D.W. Oct 5 '15 at 0:49
  • $\begingroup$ @D.W what about my algorithm ? What's your point of view ? Is it ok? $\endgroup$ – user40545 Oct 5 '15 at 17:11
  • $\begingroup$ I'm sorry I didn't address your question about your the recurrence relation specifying the time complexity of your algorithm. I've edited my post accordingly, and I hope it helps. You haven't specified a concrete algorithm in your post, so I can't verify that what you have in mind is related to the recursive function you posted, and I can't quickly come up with an $O(lg(n))$ algorithm myself, so if you can provide that, we can have a more in-depth conversation about a proper recurrence relation. $\endgroup$ – Lieuwe Vinkhuijzen Oct 5 '15 at 17:37
  • $\begingroup$ I edited my post $\endgroup$ – user40545 Oct 5 '15 at 17: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.