GATE CS 1999 Q2.24 — Asymptotic Worst Case Time and Space Complexity

Let us analyze the behavior of the function Trial(a, b, c):

• Base Case: The condition (a >= b) && (c < b) represents the ordering $a \ge b > c$. In this case, $b$ is the middle (median) element, and the function correctly returns $b$.
• Recursive Step 1: If $a < b$, the function calls Trial(b, a, c) to swap $a$ and $b$ so that the first argument is greater than or equal to the second.
• Recursive Step 2: If $a \ge b$ but $c \ge b$, the function calls Trial(a, c, b) to swap $b$ and $c$.

However, the function fails to terminate for certain inputs where $b = c$. For example, consider Trial(2, 1, 1):

1. Since $a \ge b$ ($2 \ge 1$) is true but $c < b$ ($1 < 1$) is false, the base condition is not met.
2. The else if (a >= b) condition ($2 \ge 1$) is true, so it calls Trial(a, c, b), which is Trial(2, 1, 1).
3. This results in an infinite recursion (stack overflow).

Since the function does not terminate for all inputs, it does not correctly find the middle number. Thus, the correct option is D.