# Solving recurrences (tree method) with square roots

I am trying to find the upper and lower bounds for this recurrence, but I am not sure how to handle to square root: $$T(n) = 4T(n/2) + n^2\sqrt{n}$$

• $n^2 \cdot \sqrt{n} = n^{5/4}$, then you proceed as normal. Master Theorem should work here.
– ryan
Sep 27 '19 at 15:27
• @ryan You meant $n^2\cdot\sqrt{n}=n^{5/2}$, right? Sep 28 '19 at 2:00
• Oh yes whoops. That is what I meant.
– ryan
Sep 28 '19 at 2:32
$$n^2 \cdot \sqrt{n} = n^{5/2}$$, then you can proceed with the Master Theorem as normal.
1. Root Level : $$n^{5/2}$$
2. Next Level : $$4 \cdot (n\ /\ 2)^{5/2} = 2^{4/2} \cdot n^{5/2}\ /\ 2^{5/2} = n^{5/2}\ /\ 2^{1/2}$$
3. Next Level : $$16 \cdot (n\ /\ 4)^{5/2} = 4^{4/2} \cdot n^{5/2}\ /\ 4^{5/2} = n^{5/2}\ /\ 4^{1/2}$$