patternMinor
Counting inversion pairs
Viewed 0 times
pairsinversioncounting
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#3200, answer score: 3
Revisions (0)
No revisions yet.