Suppose we have a permutation $\pi$ on $1,2,\ldots,n$ and want to determine the parity (odd or even) of $\pi$.

The standard method is find the cycles of $\pi$ and recall that the parity of $\pi$ equals the parity of the number of cycles of even length. However this seems to require $\Theta(n)$ bits of additional memory to carry out in linear time. (As you trace each cycle, you need to mark its elements so that you can avoid tracing the same cycle again.)

Alternatively, using only $O(\log n)$ bits (a few integer indexes), the inversions can be counted. This takes $\Theta(n^2)$ time, using the naive algorithm.

So my question: can the parity be determined in $O(n)$ time and $O(\log n)$ bits?

I have in mind that the input is a read-only array $p$ where $p[i]=\pi(i)$. An interesting variation is to allow the array to be modified. But you can't assume each array element has more than enough bits to hold the integer $n$ or else you need to count the extra bits as working space and linear time becomes easy.

Suppose we have a permutation $\pi$ on $1,2,\ldots,n$ and want to determine the parity (odd or even) of $\pi$.

The standard method is find the cycles of $\pi$ and recall that the parity of $\pi$ equals the parity of the number of cycles of even length. However this seems to require $\Theta(n)$ bits of additional memory to carry out in linear time. (As you trace each cycle, you need to mark its elements so that you can avoid tracing the same cycle again.)

Alternatively, using only $O(\log n)$ bits (a few integer indexes), the inversions can be counted. This takes $\Theta(n^2)$ time, using the naive algorithm.

So my question: can the parity be determined in $O(n)$ time and $O(\log n)$ bits?

I have in mind that the input is a read-only array $p$ where $p[i]=\pi(i)$. An interesting variation is to allow the array to be modified. But you can't assume each array element has more than enough bits to hold the integer $n-1$ (not $n$, because I want only the values $1,\ldots,n$ to be representable; you don't get an additional value to use as a marker) or else you need to count the extra bits as working space and linear time becomes easy.

Suppose we have a permutation $\pi$ on $1,2,\ldots,n$ and want to determine the parity (odd or even) of $\pi$.

The standard method is find the cycles of $\pi$ and recall that the parity of $\pi$ equals the parity of the number of cycles of even length. However this seems to require $\Theta(n)$ bits of additional memory to carry out in linear time. (As you trace each cycle, you need to mark its elements so that you can avoid tracing the same cycle again.)

Alternatively, using only $O(\log n)$ space (a few integer indexes), the inversions can be counted. This takes $\Theta(n^2)$ time, using the naive algorithm.

So my question: can the parity be determined in $O(n)$ time and $O(\log n)$ space?

Suppose we have a permutation $\pi$ on $1,2,\ldots,n$ and want to determine the parity (odd or even) of $\pi$.

The standard method is find the cycles of $\pi$ and recall that the parity of $\pi$ equals the parity of the number of cycles of even length. However this seems to require $\Theta(n)$ bits of additional memory to carry out in linear time. (As you trace each cycle, you need to mark its elements so that you can avoid tracing the same cycle again.)

Alternatively, using only $O(\log n)$ bits (a few integer indexes), the inversions can be counted. This takes $\Theta(n^2)$ time, using the naive algorithm.

So my question: can the parity be determined in $O(n)$ time and $O(\log n)$ bits?

I have in mind that the input is a read-only array $p$ where $p[i]=\pi(i)$. An interesting variation is to allow the array to be modified. But you can't assume each array element has more than enough bits to hold the integer $n$ or else you need to count the extra bits as working space and linear time becomes easy.