  We assume the permutation $\pi$ is given by an $n$-element array in which the
$i$-th element denotes the value $\pi(i)$. Constructing its inverse in-place
(i.e. using $O(\log{n})$ bits of additional memory) can be achieved in linear
time with a simple algorithm. Limiting the numbers that can be stored in our
array to the range $[1...n]$ still allows a straightforward $O(n^2)$ time
solution. The time complexity can be improved using randomization, but this
only improves the expected, not the pessimistic running time. We present a
deterministic algorithm that runs in $O(n^{3/2})$ time.
