Help with a recurrence relation

Question

I have been battling with the following:

$$T\left(n\right)=3T\left(\frac{n}{2}\right)+n\log(n)$$

I have tried expanding it but the term $n\log(n)$ gets very messy. What is the approach for solving this recurrence?

Answer 1

If you have encountered the Master Theorem, then this is an extremely easy solution. Since this is of the form:

$ T(n) = aT(\frac{n}{b}) + f(n) $

$a = 3$, $b = 2$, and $f(n) = n\log n$. $f(n) = O( n^{\log_2 3} - \epsilon)$, which means case 1 applies and $T(n) = O(n^{\log_2 3})$

Answer 2

$T(n)=O(n^{\log_2 3})$

To see why, first consider what happens if the $n\log n$ term is missing. Then we get $T(n)=O(n^{\log_2 3})$. Now observe that $n^{\log_2 3}>>n\log n$ asymptotically, so introducing the $n\log n$ doesn't change the asymptotics.