$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
$\begingroup$
$\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$– Ramesses2Commented 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$– ryanCommented Jul 14, 2020 at 18:11
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ Unfortumately, the original post has been edited to make your answer invalid. $\endgroup$ Commented 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$– ryanCommented Jul 14, 2020 at 18:18
$\begingroup$
$\endgroup$
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.
