Timeline for Number of levels in the recursion tree
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 19, 2016 at 10:00 | comment | added | D.W.♦ | @Romy, it's because your line of reasoning is only valid when $b$ is a constant. If you're still confused, I suggest you try writing down a careful justification for why your line of reasoning should be valid, and then you might discover at what step it goes awry; if not, edit the question with that detailed reasoning to give us something concrete to respond to. | |
| Jan 19, 2016 at 9:02 | comment | added | Romy | I understood what you said but actually I wrote $T\left ( n \right ) = a\cdot T\left ( \sqrt{n} \right ) + c$ itself as $T\left ( n \right ) = a\cdot T\left ( \frac{n}{\sqrt{n}} \right )+c$ to see that by what fraction of $n$ the problem is getting reduced with each level of the tree, so that I can easily compute number of levels by using logarithm.I don't think taking $\sqrt{n}$ as log base should be an issue as $\log_{\sqrt{n}}n= \frac{\log_{2}n}{\log_{2}{\sqrt{n}}}$.Could you please tell me what went wrong here, why my estimation for number of levels is wrong? | |
| Jan 18, 2016 at 19:57 | history | answered | D.W.♦ | CC BY-SA 3.0 |