Is there an O(n) algorithm for parity of a permutation? If not, why not?
I found the following O(n) algorithm (coded in Maple) on http://www.math.rwth-aachen.de/mapleAnswers/html/502.html: [As a non-maple-user I assume that ll is the initial permutation, and n is the number of its elements] # parity returns the parity of a permutation of a list of integers # from 1 to n, relative to the standard permutation 1,2,...,n. # It returns 1 for even parity, -1 for odd parity. parity := proc(l::list(posint)) local i,j,ll,n,p; ll := table(l); n := nops(l); i := 1; # i points to the next element to check p := 1; # p keeps track of the parity while i < n do # don't need to check case i=n, it must be right. j := ll[i]; if i <> j then p := -p; ll[i] := ll[j]; ll[j] := j else i := i+1 fi od; p end: enjoy it :-) Christoph