0
$\begingroup$

$T(n) = \sqrt{2}T(\frac{n}{2}) + \sqrt{n}$

I am trying to solve this question by recursion tree method, do we have any way in which we can draw a recursion tree for this eqn.

I just don't want to use master or extended master theorem

$\endgroup$
2
  • $\begingroup$ I don't see a choice there, you can't solve it using Master's Theorem anyway, not in this form. $\endgroup$
    – Ramesses2
    Jul 14, 2020 at 4:49
  • $\begingroup$ Are you required to use the recursion tree method? There may be other methods that are easier. $\endgroup$
    – ryan
    Jul 14, 2020 at 18:11

2 Answers 2

1
$\begingroup$

If you apply the recursive formula again to $T(n/2)$ you get the following: $$ T(n) = \sqrt{2}\cdot T(n/2) + \sqrt{n} \\T(n)= \sqrt{2}(\sqrt{2}\cdot T(n/4) + \sqrt{n/2}) + \sqrt{n} \\T(n)= 2\cdot T(n/4) + 2\sqrt{n}$$

For this formula you are now probably able to draw a recursion tree.

$\endgroup$
2
  • $\begingroup$ Unfortumately, the original post has been edited to make your answer invalid. $\endgroup$ Feb 16, 2020 at 2:04
  • $\begingroup$ @RickDecker yes the edit appears to have changed the question entirely. I believe it should be edited back to match this. $\endgroup$
    – ryan
    Jul 14, 2020 at 18:18
0
$\begingroup$

The first step is that you go and evaluate T(1024) by hand. You will find a factor $2^{27.5}$ in there and a lot more. Figure out the pattern, write down a conjecture what $T(2^k)$ would be, and prove it.

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