Computer Science Canada Recursion Trees with Recurrences |
| Author: | damasgate [ Thu Sep 30, 2010 9:17 pm ] |
| Post subject: | Recursion Trees with Recurrences |
Hello I am asked to find the Recurrece of the following algorithm T(n) = sqrt(n) T (sqrt[n]) + 100n Now, usually I would use substitution to solve this. But It has been recommended to me that I should use recursion trees. However, all the example I deal with do not have a the same form of T(n) by multiplied by a factor of n. usually it is of the form T(n)=aT(n)+ f(n). So I can't really even make out the height of the tree So how could I start this? |
|
| Author: | A.J [ Fri Oct 01, 2010 12:18 am ] |
| Post subject: | RE:Recursion Trees with Recurrences |
Hmm...this one is actually quite complicated. I believe to have gotten the answer, though I wouldn't know how you would go about solving this using recursion trees. Out of curiosity, where did you get this question? |
|
| Author: | Brightguy [ Fri Oct 01, 2010 3:59 am ] |
| Post subject: | Re: Recursion Trees with Recurrences |
Suppose n is a double exponential power of two, n = 2^(2^k), and the answer works out quite nicely. |
|