Well, if our "atoms" are indeed integers, then it takes O(n) operations to turn a permutation represented as a sequence of n integers into a permutation represented as a list of its cycles, and vice versa. In fact, the algorithm you posted uses the former representation and just follows the cycles (without explicitly generating them) and accumulates the parity. --ms -----Original Message----- From: math-fun-bounces+ms=alum.mit.edu@mailman.xmission.com [mailto:math-fun-bounces+ms=alum.mit.edu@mailman.xmission.com]On Behalf Of Pacher Christoph Sent: Sunday, December 17, 2006 11:48 To: math-fun Subject: AW: [math-fun] Permutations
I suppose that algorithm is O(n) if you take as O(1) examining a number with log n bits.
yes, I am thinking this is what Fred had in mind, because he was talking about an O(n log n) algorithm which "essentially sorts the permutation". And sorting integers takes O(n log n) comparisons and swaps of integers (not bits). But I might be completely wrong, Fred? Christoph