GATE CS 2021 Set 2 Q.49 (CS Q.39): Asymptotic Analysis and Time/Space Complexity

For constants $a \ge 1$ and $b > 1$ , consider the following recurrence defined on the non-negative integers:

T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n)

Which one of the following options is correct about the recurrence $T(n)$ ?

If $f(n)$ is $n \log_2(n)$ , then $T(n)$ is $\Theta(n \log_2(n))$ .

If $f(n)$ is $\dfrac{n}{\log_2(n)}$ , then $T(n)$ is $\Theta(\log_2(n))$ .

If $f(n)$ is $O(n^{\log_b(a) - \epsilon})$ for some $\epsilon > 0$ , then $T(n)$ is $\Theta(n^{\log_b(a)})$ .

If $f(n)$ is $\Theta(n^{\log_b(a)})$ , then $T(n)$ is $\Theta(n^{\log_b(a)})$ .

Official answer and solution

Official answer: C
From: Official GATE 2021 answer key

Solution

Match the recurrence with the standard cases of the Master Theorem.

The recurrence is given by $T(n) = a \cdot T(n/b) + f(n)$ for constants $a \ge 1$ and $b > 1$ .

In the Master Theorem, the critical exponent is $c_{\text{crit}} = \log_b a$ , and the watershed function is $n^{\log_b a}$ .

Case 1 of the Master Theorem states:
If $f(n) = O(n^{\log_b(a) - \epsilon})$ for some constant $\epsilon > 0$ , then the work at the leaves dominates the total cost, and:

T(n) = \Theta(n^{\log_b a})

This precisely matches option C.

Why other options are incorrect:

In option D, when $f(n) = \Theta(n^{\log_b a})$ , Case 2 applies, giving $T(n) = \Theta(n^{\log_b a} \log n)$ , not $\Theta(n^{\log_b a})$ .
Options A and B make unjustified assertions that depend on the specific values of $a$ and $b$ .

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 49 of 65, printed as CS Q.39
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source