Solving a recurrence relation with ���n as parameter

Question Detail: 

Consider the recurrence

$\qquad\displaystyle T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + c\,n$

for $n \gt 2$ with some positive constant $c$, and $T(2) = 1$.

I know the Master theorem for solving recurrences, but I'm not sure as to how we could solve this relation using it. How do you approach the square root parameter?

Asked By : KodeSeeker

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6410

Answered By : Peter Shor

We will use Raphael's suggestion and unfold the recurrence. In the following, all logarithms are base 2. We get

$$ \begin{align*} T(n) &= n^{1/2} T(n^{1/2}) + cn \\ &= n^{3/4} T(n^{1/4}) + n^{1/2} c n^{1/2} + cn\\ &= n^{7/8} T(n^{1/8}) + n^{3/4} c n^{1/4} + 2cn\\ &= n^{15/16} T(n^{1/16}) + n^{7/8} c n^{1/8} + 3cn \\ & \ldots \\ &= \frac{n}{2} T(2) + c n \beta(n) \end{align*}. $$ where $\beta(n)$ is how many times you have to take the square root to start with n, and reach 2. It turns out that $\beta(n) = \log \log n$. How can you see that? Consider: $$ \begin{align*} n &= 2^{\log n}\\ n^{1/2} &= 2^{\frac{1}{2} \log n} \\ n^{1/4} &= 2^{\frac{1}{4} \log n} \\ \ldots \end{align*} $$ So the number of times you need to take the square root in order to reach 2 is the solution to $\frac{1}{2^t} \log n \approx 1$, which is $\log \log n$. So the solution to the recursion is $c n \log \log n + \frac{1}{2}n$. To make this absolutely rigorous, we should use the substitution method and be very careful about how things get rounded off. When I have time, I will try to add this calculation to my answer.