How to solve this recurrence relation: $T(n)=n⋅T(\sqrt n)+O(1)$?

Question

How to solve this recurrence relation: $T(n)=n⋅T(\sqrt n)+O(1)$? I tried to use telescoping to substract, but I get stucked.. $T(n) = nT(\sqrt n)+ O(1)$
$T(n) = nT(\sqrt n) + c$
$T(n) = n(\sqrt nT(n^{1/4}) + c)+ c$
$T(n) =n^{3/2}T(n^{1/4}) + nc+ c$
$T(n) =n^{3/2}(n^{1/4}T(n^{1/8}) + c) + nc+ c$
$T(n) = n^{7/4}T(n^{1/8}) + n^{3/2}c + nc+ c$
$T(n) = n^{7/4}(n^{1/8}T(n^{1/8}) + c) + n^{3/2}c + nc+ c$
...

Answer 1

So this is a pretty crummy bound, but it's something... There's only one step that isn't sharp, and maybe someone else can help tighten it. My guess is that there's no way to be both tight and closed form, though :/

$T(n) = n T(n^{\frac{1}{2}}) + O(1)$

Substitute $n = 2^{2^k}$

$T(2^{2^k}) = 2^{2^k} T(2^{2^{k-1}}) + O(1)$.

Set $S(k) = T(2^{2^k})$

$S(k) = 2^{2^k} S(k-1) + O(1)$

But we know how to solve this!

$S(k) = 2^{2^k} + 2^{2^k} \cdot 2^{2^{k-1}} + 2^{2^k} \cdot 2^{2^{k-1}} \cdot 2^{2^{k-2}} + \ldots + \Pi 2^{2^i}$

In "closed form":

$S(k) = \sum \limits_{i=0}^k \prod \limits_{j=0}^i 2^{2^{k-j}}$

Now, if we want the bound to be clean:

$S(k) \in O \left ( k*2^{2^{k+1}} \right )$

Substituting back in, we see

$T(n) \in O \left ( n^2 \log(\log(n)) \right )$

Unfortunately, the wild overestimation really shows - this bound is awful.

If we instead substitute without the overestimation, we retrieve

$T(n) \in O \left ( \sum \limits_{i=0}^{\log(\log(n))} \prod \limits_{j=0}^i n^{2^{-j}} \right )$

A decidedly ugly bound.

If we try to clean it up, noticing $\prod \limits_{j=0}^i n^{2^{-j}} \approx n^2$ for large $i$, we again recover

$T(n) \in O \left ( n^2 \log(\log(n)) \right )$

---

Hope this helps ^_^