Why does an in-place array reversal need only n/2 swaps rather than n?

## What the operation is Reversing an array in place means rewriting the same storage so the element at index 0 ends at index n-1, index 1 ends at n-2, and so on, without allocating a second array of size n. The canonical shape is two indices walking toward each other: `i` at 0, `j` at `n-1`, swap while `i < j`, then step `i` forward and `j` backward. ## Why the swap count is n/2 A swap is a two-for-one operation. A single `swap(a[i], a[j])` puts `a[i]` into its final position *and* `a[j]` into its final position simultaneously. There are n positions to fix, each swap fixes two, so n/2 swaps (rounded down) fix all of them. The rounding matters: when n is odd, the middle index's mirror is itself, that element is already where it belongs, and no swap is spent on it. ## The invariant that makes it obvious Before each test of the loop condition: - `a[0..i-1]` and `a[j+1..n-1]` already hold their final, reversed values. - `a[i..j]` still holds the original elements in their original relative order. Each iteration extends the finished prefix and the finished suffix by one element each, and shrinks the untouched middle by two. Termination is guaranteed because the middle shrinks every iteration. When the loop exits, the middle has size 0 (even n) or size 1 (odd n), and a middle of size 1 is already correct by definition. ## The bug this question aims at The most common wrong answer is a loop over the whole range: ``` for i in 0..n-1 swap(a[i], a[n-1-i]) ``` This is symmetric: the pair (i, n-1-i) is swapped once when the counter reaches `i`, and swapped a second time when the counter reaches `n-1-i`. A pair swapped twice is back where it started, so the loop returns the *original* array (with an odd-length middle element pointlessly swapped with itself). The code reads plausibly, compiles, never throws, and silently produces wrong output — which is exactly why interviewers ask about the bound instead of asking you to define reversal. ## Costs, stated precisely Time is O(n): n/2 swaps, each constant-time for fixed-size elements. Writing "O(n/2)" is not meaningful notation — constant factors are dropped, so n/2 swaps is O(n). Extra space is O(1): two index variables plus the single temporary cell inside the swap. That temporary is reused every iteration and does not grow with n, so it does not break the in-place claim. O(1) here refers to *auxiliary* space; the array itself is storage you were given permission to modify. One caveat worth having ready: the same reversal written recursively — swap the ends, then recurse on `(i+1, j-1)` — is equally correct and still O(n) time, but its recursion depth is n/2 frames, and stack depth counts as space. Unless those frames are eliminated, the recursive form is O(n) space and no longer in place. Recursion depth is space is a rule that catches many candidates who have just finished claiming O(1). ## Range reversal is the real primitive In practice you write `reverse(a, lo, hi)` rather than a whole-array version, using `(hi - lo + 1)/2` swaps. Rotations, block moves, and word-order reversals are all assembled from two or three range reversals, so the sub-range form is the building block worth memorising. It must tolerate a degenerate empty range (`lo > hi`) without touching anything, because callers routinely pass boundaries that collapse at the edges of their input. ## Why the access pattern is friendly Two streams walking toward each other from both ends are close to the most hardware-friendly pattern there is: both are sequential, both are predictable, and prefetching handles them well. That matters later, when you compare reversal-based rotation against cleverer schemes that touch memory in a scattered order. It also shifts the cost model when elements are large records rather than small handles: then the byte cost of moving each element, not the index arithmetic, dominates.