UGC NET CSE | October 2022 | Part 1 | Question: 6

Question

The solution of the recurrence relation $T(n)=3 T(n / 4)+n \lg n$ is

• A. $\theta\left(n^{2} \lg n\right)$
• B. $\theta(n \lg n)$
• C. $\theta(n \lg n)^{2}$
• D. $\theta(n \lg \lg n)$

Comments

here  a=3  b=4  k=1   p=1which is greater than 0

Apply master theorem   here   a=3     b^k=4

a<b     and p>=0

apply third condition of master theorem   ans should be theta(n^klogn^p)=theta(nlogn)