Given an unsorted array $A$ that contains $n$ elements of numbers. Also $A$ partitioned to $k$ lists $A_1,A_2,A_3,\dots,A_k$, each contains at most nearly $\frac{n}{k}$ elements. We choose exactly one elements from each $A_i$ so that difference between maximum and minimum element minimized. Can this be done in $O(n\log k)$ time?

I think this can't be done in better than $\Omega (n\log n)$ because assume already we know the value of our optimal solution, name it $t$. Also assume $A$ not partitioned and our goal is find two elements $a$ and $b$ from $A$ such $|a-b|=t$. We know that the lower bound of a such problem is $\Omega (n\log n)$. Could we say my argument is true or not?

  • 1
    $\begingroup$ Your argument is in right direction, however, it is not completely formal. There are $k$ partitions; and you have used the same notation in $|a-b| = k$. I am assuming, you are considering $k = 1$ partitions for proving your lower bound argument. Also, this lower bound is only for comparison based model. $\endgroup$ Mar 1 at 11:59


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.