Ok, I think I see what you mean. The analysis seems pretty clear to me though. Could you specify which of the parts is the one you don’t understand?

Viewing it this way, we always apply the Bessie shuffle to the first M elements and then shift the whole permutation left. These two steps can be viewed as permutations on N elements, and the effect of them taken together (their composition) is also a permutation.

So for the sample case, `[1 2 3 4 5] -> [2 3 1 4 5] -> [3 1 4 5 2]`

.

This means we can calculate a single permutation which we need to apply (N-M+1) times to 1…N.

We want to find the 5-3+1=3'rd power of `[3 1 4 5 2]`

. (Here, applying K times to 1\ldots N = K-th power.)

To do this we can use repeated squaring, thus solving the problem in O(N log(N - M)) time.

The relevant powers of `[3 1 4 5 2]`

are:

`[3 1 4 5 2]^0 = [1 2 3 4 5]`

`[3 1 4 5 2]^1 = [3 1 4 5 2]`

(`[3 1 4 5 | 2]`

)

`[3 1 4 5 2]^2 = [4 3 5 2 1]`

(`[4 3 5 | 2 1]`

)

`[3 1 4 5 2]^3 = [5 4 2 1 3]`

(`[5 4 | 2 1 3]`

)

Of course, we need to cancel those N-M+1 left shifts with an N-M+1 right shift.

To get the final order, we shift `[5 4 2 1 3]`

N-M+1 units to the right to get `[2 1 3 5 4]`

. Then we reverse it to get `[4 5 3 1 2]`

, which is what we want.

In that problem we are also computing the K-th power of a permutation.