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
• @ryan Please post answers in the answer box, not as comments. Sep 28 '19 at 9:04

$$n^2 \cdot \sqrt{n} = n^{5/2}$$, then you can proceed with the Master Theorem as normal.

If you specifically need to use the Recursion Tree Method for solving recurrences, then you can still proceed normally.

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}$$
4. etc.