For constants $a≥1$ and $b>1$, consider the following recurrence defined…

GATE · 2021 · CS · Set 2 · Computer Science & IT

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

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

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

A.
if $f(n)$ is $n \log_2(n)$ , then $T(n)$ is $\Theta(n \log_2(n))$ .
B.
if $f(n)$ is $\dfrac{n}{\log_2(n)}$ , then $T(n)$ is $\Theta(\log_2(n))$ .
C.
if $f(n)$ is $O(n^{\log_b(a)-\epsilon})$ for some $\epsilon >0$ , then $T(n)$ is $\Theta(n^{\log_b(a)})$ .
D.
if $f(n)$ is $\Theta(n^{\log_b(a)})$ , then $T(n)$ is $\Theta(n^{\log_b(a)})$ .

Attempted by 235 students.

For constants \(a≥1\) and \(b>1\), consider the following recurrence defined…