1
$\begingroup$

The general form of my question would be, what is the most efficient way to compare the total values of two different arrays to see which one is greater?

Would be as simple as prefix sum ($O(n)$) for both arrays? Or is there a more efficient method?

The specific question I'm staring at is:

Let $A$ and $B$ be two unsorted arrays that each contains $n$ positive integers. Assume that all $2n$ integers are distinct. We say that $A$ is totally greater than $B$ if it is possible to re-order both arrays in a way that $A[i] \gt B[i]$ for every index $1 \le i \le n$. Describe an efficient algoirthm that for given arrays $A$ and $B$ determines if $A$ is totally greater than $B$.

If Prefix sum (adding $A[0]+A[1]$, then adding that sum to $A[3]$) is $O(n)$ and you have to run it twice for $O(2n)$, I don't see how you could improve on that efficiency.

All comparison sorts are $O(n(log(n))$ and Bucket Sort is $O(n)$...but this prompt would suggest there's some other efficient way to sort and compare two arrays.

$\endgroup$
17
  • 2
    $\begingroup$ Prefix sum doesn't work. You have to sort the arrays first. Try to come up with a concrete algorithm and then prove that it works. $\endgroup$ Oct 19, 2015 at 7:22
  • $\begingroup$ @YuvalFilmus Prefix sum would work if you don't care about sorting, as the prompt suggests. If I add together 4,1,3,2 to get 12 it doesn't matter what order the integers are. Otherwise I can't see anything more efficient than Quicksort / Mergesort (n log n) and an O(n) comparison traversal. $\endgroup$ Oct 19, 2015 at 14:08
  • 1
    $\begingroup$ You are asking several questions in your actual post. Can you clarify what question you are actually after? Is it the following: "Is there an $o(n\log n)$ algorithm for this problem?" $\endgroup$ Oct 19, 2015 at 14:18
  • 1
    $\begingroup$ I don't know what "total value" is. Are you looking for the most efficient solution to the highlighted text (the "specific question") or for anything else? $\endgroup$ Oct 19, 2015 at 14:22
  • 1
    $\begingroup$ I still don't understand what you mean by "compare the total values of two different arrays". In any case, any such task would take $\Omega(n)$ since it potentially depends on all elements in the array, and going over all of them necessarily takes $\Omega(m)$. $\endgroup$ Oct 19, 2015 at 14:27

0