The juggling rotation writes each element once — why does three-reversal often still win?

## The two candidates Both rotate an array in place with no auxiliary array, and both are O(n) time and O(1) extra space. **Three-reversal:** reverse the whole array, then reverse the two blocks. Three converging two-pointer scans, 2n element writes. **Juggling (cycle) rotation:** move each element directly to its destination, chasing the permutation's cycles. For a left rotation by s, the element at index i belongs at index `(i - s) mod n`, so following `i -> (i + s) mod n` walks a cycle of source positions. Save the first element, shift each successor into the hole, and close the cycle with the saved value. n element writes. ## Why there are exactly gcd(n, s) cycles Starting at index i and repeatedly adding s modulo n, you return to i after the smallest t with `t*s = 0 (mod n)`, which is `t = n / gcd(n, s)`. Every orbit therefore has the same length `n / gcd(n, s)`, and since the orbits partition all n indices, there are `gcd(n, s)` of them. That is why the outer loop runs over `0 .. gcd(n, s) - 1`: those starting points hit each cycle exactly once. When `gcd(n, s) = 1` the whole array is a single cycle; when s divides n there are s short cycles. Computing the gcd is O(log min(n, s)) — irrelevant next to the n moves, so no, juggling is not superlinear because of it. ## Where the real difference lives Since both are O(n) time and O(1) space, big-O says nothing about which to choose. Asymptotic notation is an upper bound on growth, not a promise about runtime on a particular machine, and here the growth rates are identical. The decision is made entirely by constants and by the memory hierarchy. | | three-reversal | juggling | |---|---|---| | element writes | 2n | n | | access pattern | sequential, converging | stride s, wrapping | | cache behaviour | prefetch-friendly | a miss per step once n exceeds cache | | cycles/passes | 3 passes | gcd(n, s) cycles | | review cost | three calls to a trusted primitive | cycle and gcd argument to verify | On an array comfortably inside cache, memory is effectively uniform-cost and the write count is the whole story — juggling's n moves beat 2n. Once the array is much larger than cache, each juggling step lands on an unrelated cache line, and the machine pays a miss for nearly every element; on very large or memory-mapped data the stride can also cross page boundaries constantly, adding translation misses and faults. Reversal's three passes stream through the same total bytes twice in perfectly predictable order, and predictable order is what the prefetcher rewards. Two sequential passes routinely beat one scattered pass by a wide margin. ## When juggling is the right answer - The array fits in cache, so scattering costs nothing. - Elements are large records, so the byte cost of *moving* dominates and halving the moves halves the real work. - Writes themselves are expensive relative to reads — for instance storage with limited write endurance, where write amplification is the metric being minimised. - A benchmark on the actual data says so. This is a constants question, and constants are measured, not derived. ## The judgment being tested The wrong answer is "fewer operations is faster", stated as a law. The right answer names the model the operation count assumes — uniform memory cost — and points out that the model stops holding at exactly the sizes where rotation performance starts to matter. The second half of the answer is about people: the three-reversal version is three calls to a primitive any reviewer can check, while the juggling version hides its correctness in a cycle-counting argument and an easy-to-invert direction convention. On code that will be maintained by an on-call rotation, that difference is worth more than a constant factor you have not measured.