-----------------------------------

damasgate

Thu Sep 30, 2010 9:17 pm


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?


-----------------------------------

A.J

Fri Oct 01, 2010 12:18 am


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?


-----------------------------------

Brightguy

Fri Oct 01, 2010 3:59 am


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.