Inverting Permutations In Place
Matthew Robertson · UWSpace (University of Waterloo) · 2015
We address the problem of quickly inverting the standard representation of a permutation on $n$ elements in place. First, we present a naive algorithm to do it using $O(\\log n)$ extra bits in $O(n^2)$ time in the worst case. We then improve that algorithm, using a small bit vector, to use $O(\\sqrt n)$ extra bits in $O(n \\sqrt n)$ time. Using a different approach, we present an algorithm to do it using $O(\\sqrt n \\log n)$ extra bits in $O(n \\log n)$ time. Finally, for our main result, we present a technique that leads to an algorithm to invert the standard representation of a permutation using only $O(\\log^2 n)$ extra bits of space in $O(n \\log n)$ time in the worst case.