= Solution
Count element reads and writes, ignoring simple-variable operations. A <swap> of distinct entries makes two reads and two writes, hence four expensive accesses. For $0<k<n$, the three-reversal method therefore costs
$$
4R,\qquad R=\left\lfloor\frac{n-k}{2}\right\rfloor+\left\lfloor\frac{k}{2}\right\rfloor+\left\lfloor\frac n2\right\rfloor.
$$
Here $R=n$ if $n$ and $k$ are both even, and $R=n-1$ otherwise.
For either block-exchange version, let $a=n-k$, $b=k$, and let $S(a,b)$ count element swaps. The recurrence is $S(a,a)=a$ and, when the lengths differ,
$$
S(a,b)=\min(a,b)+S\bigl(\min(a,b),|a-b|\bigr).
$$
The <Euclidean algorithm> preserves $\gcd(a,b)$ under this subtraction. <Induction> on $a+b$ therefore yields
$$
S(a,b)=a+b-\gcd(a,b)=n-\gcd(n,k).
$$
Thus both block-exchange methods cost \b[$4(n-\gcd(n,k))$ accesses], no more than the three-reversal method. Their element-access counts are identical; the iterative one avoids the recursive stack. For example a half-length rotation uses $n/2$ swaps instead of approximately $n$ reversal swaps.
Each single-place pass in part (iv) reads every entry once and writes every entry once, costing \b[$2nk$ accesses]. For $k=1$, its $2n$ accesses beat the block method's $4(n-1)$ for $n>2$ and tie for $n=2$. For $k\geq2$ the block method costs strictly less than $2nk$. All three methods as written return without accesses for $k=0$ or $k=n$. \b[Repeated shifting can take quadratic time; the reversal and block methods take linear time.] These comparisons concern the specified implementations, not a more general cycle-decomposition rotation using several disjoint cycles.
Back to article page
