Solving the recurrence $T(n) = 3T(n/4) + n\log n , T(1) = 1$

Question

Solve the recurrence $T(n) = 3T(n/4) + n\log n , T(1) = 1$

Can someone help me to solve this recurrence using substitution method?

Answer 1

Use the master method. Let $$T(n) = aT\left(\dfrac nb\right) + f(n).$$ Therefore, we have that $a = 3, b = 4,$ and $f(n) = n\log n$. Then, $n^{\log_ba} = n^{\log_43} \simeq n^{0.792}$. It is clear that $f(n) = n\log n > n^{0.792}$ as $n\to\infty$, and we can thus eliminate the first and second cases of the master method. Next, you can show that $\forall \varepsilon$ such that $\log_43\le\log_43+\varepsilon \le 1$, $f(n)\in\Omega\left(n^{\log_ba + \varepsilon}\right) = \Omega\left(n^{0.792 + \varepsilon}\right)$, and therefore, $T(n)\in\Theta\left(f(n)\right) = \Theta(n\log n)$.