0
$\begingroup$

Suppose given $k$-sorted arrays of numbers that contains total of $n$ elements. we try to choose $k$ elements in $k$ arrays (each arrays exactly one element) such that minimize difference between maximum and minimum number in chosen $k$ numbers. What is lower bound of this problem? I have an algorithm that solve above problem in $\Omega(n\log k)$.

I think this problem related to $k$-way merge. And already I know why the lower bound of $k$-way merge is $\Omega(n\log k)$. But I can't reduce $k$-way merge to above problem.

Improve this question
$\endgroup$
4
  • $\begingroup$ What is your computation model? Linear decision trees? $\endgroup$
    – Yuval Filmus
    Apr 16, 2022 at 12:35
  • $\begingroup$ @YuvalFilmus I try to find a lower bound under comparison based models. $\endgroup$
    – ErQ65
    Apr 16, 2022 at 13:27
  • 1
    $\begingroup$ I’m not sure that the vanilla comparison model can solve your problem. $\endgroup$
    – Yuval Filmus
    Apr 16, 2022 at 13:58
  • $\begingroup$ cs.stackexchange.com/q/150610/755 $\endgroup$
    – D.W. ♦
    Apr 24, 2022 at 5:57

0

Reset to default

Browse other questions tagged or ask your own question.