GATE CS 2000 Q2.15 — Asymptotic Worst Case Time and Space Complexity

To understand the effect of the given sequence of operations, let us represent the array $s[1…n]$ as the concatenation of two subarrays, $A$ and $B$:

• $A = s[1…k]$ of length $k$
• $B = s[k+1…n]$ of length $n-k$

Thus, the initial array is $s = AB$.

Let $X^R$ denote the reversal of a sequence $X$. Let's trace the operations step-by-step:

1. reverse(s, 1, k): Reverses the first $k$ elements (subarray $A$).
   The array becomes: $A^R B$
2. reverse(s, k+1, n): Reverses the remaining $n-k$ elements (subarray $B$).
   The array becomes: $A^R B^R$
3. reverse(s, 1, n): Reverses the entire array.
   The reversal of the concatenated sequence $A^R B^R$ is: $$(A^R B^R)^R = (B^R)^R (A^R)^R = BA$$ The array becomes: $BA$

Since the initial array $AB$ has been transformed into $BA$, the first $k$ elements have moved to the end, and the remaining elements have shifted to the front. This is precisely a left rotation of $s$ by $k$ positions.

Example:

Let $s = [1, 2, 3, 4, 5]$ with $n = 5$ and $k = 2$.

• After reverse(s, 1, 2): $s = [2, 1, 3, 4, 5]$
• After reverse(s, 3, 5): $s = [2, 1, 5, 4, 3]$
• After reverse(s, 1, 5): $s = [3, 4, 5, 1, 2]$

This is a left rotation of the original array by $2$ positions, confirming that Option A is correct.