Q39

MCQ2 marks, −0.67

For constants $a \geq 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)})$

Loading…