1
$\begingroup$

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} $$

$\endgroup$
4
  • 5
    $\begingroup$ $n^2 \cdot \sqrt{n} = n^{5/4}$, then you proceed as normal. Master Theorem should work here. $\endgroup$
    – ryan
    Sep 27, 2019 at 15:27
  • $\begingroup$ @ryan You meant $n^2\cdot\sqrt{n}=n^{5/2}$, right? $\endgroup$ Sep 28, 2019 at 2:00
  • $\begingroup$ Oh yes whoops. That is what I meant. $\endgroup$
    – ryan
    Sep 28, 2019 at 2:32
  • 1
    $\begingroup$ @ryan Please post answers in the answer box, not as comments. $\endgroup$ Sep 28, 2019 at 9:04

1 Answer 1

1
$\begingroup$

$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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.