4
$\begingroup$

I'm looking for a one-pass algorithm which computes parity of a permutation. I assume that an input permutation is given by stream $\pi[1], \pi[2], \cdots, \pi[n]$. The output should be the parity of the permutation. The question I'm interested in how much memory deterministic algorithm should use.

I know that computing number of inversions in one pass uses $\Theta(n)$ memory. The upper bound can be easily obtained with any BST. The lower bound is presented here: http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.112.5622

Alas, the proof of thelower bound in the paper can not be extended to the parity case (or it's not so obvious to me).

Does anybody know an effective algorithm or lower bound on memory for computing parity? Randomized algorithms better than random coin are interesting to me too. =)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.