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} $$
$\begingroup$
$\endgroup$
4
-
5$\begingroup$ $n^2 \cdot \sqrt{n} = n^{5/4}$, then you proceed as normal. Master Theorem should work here. $\endgroup$– ryanCommented Sep 27, 2019 at 15:27
-
$\begingroup$ @ryan You meant $n^2\cdot\sqrt{n}=n^{5/2}$, right? $\endgroup$– Rick DeckerCommented Sep 28, 2019 at 2:00
-
$\begingroup$ Oh yes whoops. That is what I meant. $\endgroup$– ryanCommented Sep 28, 2019 at 2:32
-
1$\begingroup$ @ryan Please post answers in the answer box, not as comments. $\endgroup$– David RicherbyCommented Sep 28, 2019 at 9:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
$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.
- Root Level : $n^{5/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}$
- Next Level : $16 \cdot (n\ /\ 4)^{5/2} = 4^{4/2} \cdot n^{5/2}\ /\ 4^{5/2} = n^{5/2}\ /\ 4^{1/2}$
- etc.
