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 '20 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 '20 at 18:11
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$ – Rick Decker Feb 16 '20 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 '20 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, privacy policy and cookie policy

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