GATE CS 2004 Q41 — Asymptotic Worst Case Time and Space Complexity

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

Step-by-Step Analysis:

• The program initializes $m = x$ and $n = y$.
• The while(m != n) loop continues as long as $m$ and $n$ are not equal.
• Inside the loop:
  • If $m > n$, it replaces $m$ with $m - n$. This is based on the mathematical property:
    $$\gcd(m, n) = \gcd(m - n, n) \quad \text{for } m > n$$
  • If $n > m$, it replaces $n$ with $n - m$, based on:
    $$\gcd(m, n) = \gcd(m, n - m) \quad \text{for } n > m$$
• When $m$ becomes equal to $n$, the loop terminates, and the common value (which is $\gcd(x, y)$) is printed.

Example Trace:

Let $x = 15$ and $y = 9$:

1. Initially, $m = 15, n = 9$. Since $m \neq n$:
   • $m > n \implies m = 15 - 9 = 6$.
2. Now, $m = 6, n = 9$. Since $m \neq n$:
   • $n > m \implies n = 9 - 6 = 3$.
3. Now, $m = 6, n = 3$. Since $m \neq n$:
   • $m > n \implies m = 6 - 3 = 3$.
4. Now, $m = 3, n = 3$. Since $m == n$, the loop terminates.
5. The program prints $n = 3$, which is indeed $\gcd(15, 9)$.

Therefore, the program computes the greatest common divisor of $x$ and $y$.