14
$\begingroup$

A classic application of divide and conquer is to solve the following problem:

Given an array $a[1\dots n]$ of distinct, comparable elements, count the number of inversion pairs in the array: pairs $(i,j)$ such that $a[i] \gt a[j]$ and $i \lt j$.

One approach to this is to do a Merge Sort, but also counting of the number of inversion pairs in the sub-problems. During the merge step, we count the number of inversion pairs that span across the (two) sub-problems and add to the counts of the sub-problems.

While this is good, and gives an $O(n\log n)$ time algorithm, this messes up array.

If we have the additional constraint that the array is read-only, then we can make a copy and deal with the copy, or use an additional data-structure like an order statistics balanced binary tree to do the counting, both of which use $\Theta(n)$ space.

The current question is to try and better the space, while not affecting the run time. i.e.

Is there an $O(n\log n)$ time algorithm to count the number of inversion pairs, which works on a read-only array and uses sub-linear (i.e. $o(n)$) space?

Assume a uniform cost RAM model and that the elements take $O(1)$ space and comparison between them is $O(1)$.

A reference will do, but an explanation will be better :-)

I tried searching the web, but could not find any positive/negative answer for this. I suppose this is just a curiosity.

$\endgroup$
  • 3
    $\begingroup$ Chan and Pătraşcu give an $o(n \log n)$ time algorithm, but as far as I can tell from skimming the paper, they need $\Omega(n)$ space. $\endgroup$ – Raphael Aug 15 '12 at 21:18
  • 2
    $\begingroup$ Furthermore, Ajtai et al. prove that any (exact) $O(n)$ time streaming algorithm needs $\Omega(n)$ space. There seem to be approximations fitting your criteria, though. $\endgroup$ – Raphael Aug 15 '12 at 21:25
  • 1
    $\begingroup$ @Raphael: Thanks! If no answer is forthcoming, your comment would be the best answer so far. $\endgroup$ – Aryabhata Aug 16 '12 at 2:35
  • $\begingroup$ BTW I am a little confused about that Ajtai et al lower bound. Theorem 8 says "any algorithm", but the lower bound to me seems to be against single pass exact streaming algorithms, a very restricted model $\endgroup$ – Sasho Nikolov Aug 16 '12 at 4:23
  • $\begingroup$ @SashoNikolov: I think they globally set their model to streaming algorithms, so "any" would be restricted to those. I hope that my corollary -- any exact $O(n)$ time algorithm -- is correct, that is that any linear-time algorithm can be expressed as a streaming algorithm with constantly many passes. We'll see. $\endgroup$ – Raphael Aug 16 '12 at 8:26
3
$\begingroup$

Here is Raphael's answer:

Chan and Pătraşcu give an $o(n\log n)$ time algorithm, but as far as I can tell from skimming the paper, they need $\Omega(n)$ space. Furthermore, Ajtai et al. prove that any (exact) $O(n)$ time streaming algorithm needs $\Omega(n)$ space. There seem to be approximations fitting your criteria, though.

$\endgroup$
  • $\begingroup$ Thanks for making it an answer. I will give it some more time though. The traffic seems to be picking up. $\endgroup$ – Aryabhata Sep 4 '12 at 16:15

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.