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. =)
