Solve the recurrence relation $ T(n) = n^{1/2}T(n^{1/2}) +3n $
My try is that:
$ T(n) = n^{1/2}T(n^{1/2}) +3n $
$ T(n) = n^{1/2}T(n^{1/4}T(n^{1/4})+3n^{1/2}) +3n $
$ . $ $ . $ $ . $
$ T(n) = n^{1-2^{-i}}T(n^{2^{-i}}) +3in $
Assume that $T(2) = 2 => n^{2^{-i}} = 2 => i = log(logn)$
And then $ T(n) = (n/2)T(2) + 3log(logn)n $
And from here $ T(n) = θ(nlog(logn)) $
But the issue is that $T(2) = 2 $ is not given. And I do not have any reason to assume $ T(2) = 2 $
Hint.
With $n>0$ we have
$$ \frac{T(n)}{n} = \frac{T\left(\sqrt{n}\right)}{\sqrt{n}}+3 $$
so calling now $R(n) = \frac{T(n)}{n}$ we have the recurrence
$$ R(n) = R\left(\sqrt{n}\right)+3 $$
but
$$ R\left(2^{\log_2 n}\right) = R\left(2^{\log_2 \sqrt{n}}\right)+3 $$
and with $\mathcal{R}(\cdot) = R\left(2^{(\cdot)}\right)$, $z = \log_2 n$ we follow with
$$ \mathcal{R}(z) = \mathcal{R}\left(\frac z2\right) +3 $$
and now with $z = 2^u$ we follow with
$$ \mathcal{R}(2^u) = \mathcal{R}\left(2^{u-1}\right) +3 $$
etc.