Is the runtime complexity $Θ\left(n^2lg\ n\right)$ for this recurrence relation $T\left(n\right)\ =\ 4T\left(\frac{n}{2}\right)\ +\ n^2\sqrt{n}$?

Question

I am using the master theorem case 2:

$f\left(n\right)\ =\ n^2\sqrt{n}\ ∈\ Θ\left(n^{\log_b\left(a\right)}\right)\ ∈\ Θ\left(n^{\log_2\left(4\right)}\right)\ ∈\ Θ\left(n^2\right)$

so it looks like the master theorem can be used:

$T\left(n\right)\ =Θ\left(n^{\log_b\left(a\right)}\ lg\ n\right)\ =\ Θ\left(n^{\log_2\left(4\right)}\ lg\ n\right)=\ Θ\left(n^2\ lg\ n\right)$

Is this right?

Answer 1

No, $n^2 \cdot \sqrt{n} \notin \Theta(n^2)$!

To be honest, even the first additive term contradicts your result: $n^2 \cdot \sqrt{n} \notin \Theta(n^2 \log n)$.

I recommend to solve this "by hand" or to choose case $3$ :-)

Answer 2

You can plug the proposal in the equation:

$$n^2\lg n\propto4\frac{n^2}{2^2}\lg\frac n2+n^2\sqrt n.$$

But

$$n^2\lg n\propto n^2\lg n-n^2+n^2\sqrt n$$ is wrong. (It remains wrong if you multiply by a constant.)