GATE CS 2023 Q44 — Asymptotic Worst Case Time and Space Complexity

To determine the correct options, let us analyze the execution counts $f_1(n)$ and $f_2(n)$ for the statement x = x + 1 in both functions.

Analysis of $\textsf{Function\_1}$:

In each iteration of the outer while loop, the value of $n$ is halved. The inner for loop runs $n$ times. Therefore, the total number of executions $f_1(n)$ is given by the sum of a geometric progression: $$f_1(n) = n + \lfloor n/2 \rfloor + \lfloor n/4 \rfloor + \dots + 1$$ Using the properties of geometric series, we have: $$n \le f_1(n) < n \sum_{i=0}^{\infty} \frac{1}{2^i} = 2n$$ Thus, $f_1(n) \in \Theta(n)$.

Analysis of $\textsf{Function\_2}$:

The loop runs exactly $100n$ times. Thus, the statement is executed: $$f_2(n) = 100n$$ This clearly means $f_2(n) \in \Theta(n)$.

Evaluating the Options:

• Option A: Since both $f_1(n)$ and $f_2(n)$ are in $\Theta(n)$, they are asymptotically equivalent. Hence, $f_1(n) \in \Theta(f_2(n))$ is TRUE.
• Option B: $f_1(n) \in o(f_2(n))$ is false because $f_1(n)$ does not grow strictly slower than $f_2(n)$ (their ratio is a non-zero constant $\approx 1/50$).
• Option C: $f_1(n) \in \omega(f_2(n))$ is false because $f_1(n)$ does not grow strictly faster than $f_2(n)$.
• Option D: Since $f_1(n) \in \Theta(n)$, it also satisfies the upper bound $f_1(n) \in O(n)$, which is TRUE.