GATE CS 2024 Set 1 — Question 48

The function updates the variable $x$ in a loop that iterates $y$ times. Let $x_i$ denote the value of $x$ after $i$ iterations, with $x_0$ being the initial input $x$. The update rule in each iteration is:$$x_{i+1} = x_i + x_i + y = 2x_i + y$$This is a linear recurrence relation. We can find the general term by observing the first few iterations:

• $x_1 = 2x_0 + y$
• $x_2 = 2(2x_0 + y) + y = 2^2 x_0 + (2+1)y$
• $x_3 = 2(2^2 x_0 + 3y) + y = 2^3 x_0 + (2^2 + 2 + 1)y$

In general, after $i$ iterations:$$x_i = 2^i x_0 + (2^i - 1)y = 2^i(x_0 + y) - y$$The function returns the value after $y$ iterations, which is $f(x, y) = 2^y(x + y) - y$.Evaluating the options:

• (A) and (C): For $x=20, y=10$, the return value is $f(20, 10) = 2^{10}(20 + 10) - 10 = 30 \cdot 1024 - 10 = 30710$.
• $30710$ is much smaller than $2^{20} = 1,048,576$, so (A) is false.
• $30710$ is greater than $2^{10} = 1024$, so (C) is false.
• (B): For $x=20, y=20$, the return value is $f(20, 20) = 2^{20}(20 + 20) - 20 = 40 \cdot 2^{20} - 20$. Since $40 \cdot 2^{20} - 20 > 2^{20}$, (B) is true.
• (D): For $x=10, y=20$, the return value is $f(10, 20) = 2^{20}(10 + 20) - 20 = 30 \cdot 2^{20} - 20$. Since $30 \cdot 2^{20} - 20 > 2^{20}$, (D) is true.

Thus, the correct options are B and D.