# How can i solve a recursion equation with square root using recursion tree method?

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

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

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