[math-fun] recognizing an even permutation

Given a permutation of {1,2,3,...,N}, in the form of a vector f(1), f(2), ..., f(N) how quickly (and using how little memory) can you decide whether it is an "even" permutation? I can see a way to do it in O(N) operations which uses only O(1) words of memory plus the memory used to store the input array f[]; but unfortunately this N-entry array will be destroyed/overwritten. I also see a way to do it in O(N^2) operations with only O(1) words of extra memory -- the input array now is unaltered. But I do not know a way to do it that uses memory*time product that is o(N^2). -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)