Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming / 4 / d / 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 costsHere $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,The Euclidean algorithm preserves $\gcd (a,b)$ under this subtraction. Induction on $a+b$ therefore yieldsThus both block-exchange methods cost $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 $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\ge 2$ the block method costs strictly less than $2nk$. All three methods as written return without accesses for $k=0$ or $k=n$. 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.