GATE CS 1995 Q2.3 — Asymptotic Worst Case Time and Space Complexity

The given program segment implements the classic Euclidean algorithm for finding the Greatest Common Divisor (GCD) of two positive integers $X$ and $Y$ using repeated subtraction.

At each step of the while loop:

• If $X > Y$, it replaces $X$ with $X - Y$.
• If $Y > X$, it replaces $Y$ with $Y - X$.

This process continues until $X = Y$. According to the properties of GCD, $\gcd(X, Y) = \gcd(X - Y, Y)$ for $X > Y$. Thus, when the loop terminates, both $X$ and $Y$ hold the value of the GCD of the original two numbers, which is then printed.