Solving the recurrence $T(n) = \sqrt n T(\sqrt{n}) + \sqrt{n}$

A former student of mine was TA-ing an algorithms class last quarter and asked students to solve this famous recurrence relation:

$$T(n) = \sqrt n T(\sqrt{n}) + n$$

There are several ways to solve this recurrence relation and this question has already been asked here.

I was talking to my student about this problem and mentioned that it's quite hard to solve and is pretty dependent on the particular choices being made. As an example, I suggested this variant of a recurrence relation that was less simple to solve:

$$T(n) = \sqrt n T(\sqrt{n}) + \sqrt{n}$$

The TA and I tried solving this recurrence for about an hour and a half without making any progress. Here are a few things we tried:

• My approach to solving the initial recurrence relation was to draw out a recursion tree and notice that each level of the tree contributes $n$ to the total and that there are $O(\log \log n)$ layers, so the recurrence solves to $O(n \log \log n)$. When I tried doing this here, I noticed that the work per layer was no longer constant; instead, the top layer sums to $\sqrt{n}$, the second layer to $n^{3/4}$, the third to $n^{7/8}$, etc. We got stuck working with the summation $n^{1/2} + n^{3/4} + n^{7/8} + ...$.

• We tried using the iteration method to unroll the recurrence. With the original recurrence relation, this works out nicely; here, we got stuck at the same summation given above.

I'm completely stuck trying to figure out how to solve this recurrence relation. There's nothing riding on it per se - I don't need to solve it for any particular reason - but the fact that we arrived at it by a straightforward modification of a common algorithms problem set question makes it all the more enticing.

Any idea how to solve this recurrence?

Thanks!

Solution 1:

As you mention, the explicit solution (assuming appropriate initial conditions) is $$ \begin{align*} T(n) &= n^{1/2} + n^{3/4} + \cdots + n^{1-1/\log n} \\ &= n \left(\frac{1}{n^{1/2}} + \frac{1}{n^{1/4}} + \cdots + \frac{1}{n^{1/\log n}} \right). \end{align*} $$ Note that $1/n^{1/\log n} = 1/2$. Another way of writing the same formula is $$ T(n) = n\left(\frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^4} + \cdots + \frac{1}{2^{2^{\log\log n-1}}} \right). $$ The infinite series $$ \sum_{k=0}^\infty \frac{1}{2^{2^k}} $$ converges to some limit $L \approx 0.81642$, and so $$ T(n) = Ln + o(n), $$ the formula holding for $n$ of the form $2^{2^k}$.