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 '19 at 15:27
  • $\begingroup$ @ryan You meant $n^2\cdot\sqrt{n}=n^{5/2}$, right? $\endgroup$ Sep 28 '19 at 2:00
  • $\begingroup$ Oh yes whoops. That is what I meant. $\endgroup$
    – ryan
    Sep 28 '19 at 2:32
  • 1
    $\begingroup$ @ryan Please post answers in the answer box, not as comments. $\endgroup$ Sep 28 '19 at 9:04
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, privacy policy and cookie policy

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