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:
In every case I dispose $1/3$ elements and get smaller problem.