What is the best method of solving non standard recurrence algorithms?
In particular something like the following:
What would be it's tight bound in Theta notation?
$$ n \in N\\ T(n) = \sqrt{n} \; T(\sqrt{n}) + 100n $$
My intuition tells me that I have to do some sort of substitution first. Something like:
$$ Let \quad m = \sqrt{n} \\ T(m^2) = m \; T(m) + 100m^2 $$
Which is a bit more tolerable, but still Is this even solvable??
Thanks a lot!
$$m=\lg n \Rightarrow n=2^m$$
$$\sqrt{n}=\sqrt{2^m}=2^{\frac{m}{2}}$$
$$T(n)=\sqrt{n}T(\sqrt{n})+100n \\ \Rightarrow T(2^m)=2^{\frac{m}{2}}T(2^{\frac{m}{2}})+100 \cdot 2^m \\ \Rightarrow \frac{T(2^m)}{2^m}=\frac{T(2^{\frac{m}{2}})}{2^{\frac{m}{2}}}+100$$
Now setting $$S(m)=\frac{T(2^m)}{2^m}$$ we have the following:
$$S(m)=S\left ( \frac{m}{2} \right )+100$$
Can you solve the last recurrence relation??