Recursion Trees with Recurrences

[damasgate]

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]

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]

Suppose n is a double exponential power of two, n = 2^(2^k), and the answer works out quite nicely.