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

discrete mathematicsrecurrence-relations

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!

Best Answer

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}$.

Related Question