GATE CS 2021 Set 2 Q23 — Asymptotic Worst Case Time and Space Complexity

The given C function implements the subtraction-based Euclidean algorithm to find the Greatest Common Divisor (GCD) of two positive integers $x$ and $y$, with an additional base case for when either number is $1$ (which also correctly returns $1$, since $\gcd(1, k) = 1$).

Let's trace the execution of SomeFunction(15, 255):

• Since $255 > 15$, the function executes SomeFunction(x, y-x), which translates to SomeFunction(15, 240).
• This subtraction step continues repeatedly because $y > x$ at each step: $$\text{SomeFunction}(15, 255) \rightarrow \text{SomeFunction}(15, 240) \rightarrow \text{SomeFunction}(15, 225) \rightarrow \dots \rightarrow \text{SomeFunction}(15, 15)$$
• When the arguments reach SomeFunction(15, 15), the condition if (x == y) is satisfied, and the function returns x, which is $15$.

Mathematically, the function computes: $$\gcd(15, 255) = 15$$

Therefore, the value returned by SomeFunction(15, 255) is 15.