Q7

MCQ1 mark, −0.33

Consider the following recurrence relations: For all $n>1$ ,

\begin{array}{c} T_{1}(n)=4 T_{1}\left(\frac{n}{2}\right)+T_{2}(n) \\ T_{2}(n)=5 T_{2}\left(\frac{n}{4}\right)+\Theta\left(\log _{2} n\right) \end{array}

Assume that for all $n \leq 1, T_{1}(n)=1$ and $T_{2}(n)=1$ . Which one of the following options is correct?

(A)

$T_{1}(n)=\Theta\left(n^{2}\right)$

(B)

$T_{1}(n)=\Theta\left(n^{2} \log _{2} n\right)$

(C)

$T_{1}(n)=\Theta\left(n^{\log _{4} 5}\right)$

(D)

$T_{1}(n)=\Theta\left(n^{\log _{4} 5} \log _{2} n\right)$

Loading…