<s>[INST] Give an asymptotic upper bound of this recurrence relation : $T(n) = 2\cdot T(n^{1/2}) + n$ I unrolled the recursion and got this:
$T(n) = 2^k\cdot T(n^{1/2^k}) + [2^0\cdot n^{1/2^0} + 2^1\cdot n^{1/2^1} + 2^2\cdot n^{1/2^2}+\cdots+2^{k-1}\cdot n^{1/2^{k-1}}]$
I considered every $n^{1/2^i}$ as $n$.
$\begin{align}
T(n)&\leq 2^k\cdot T(n^{1/2^k}) + n(2^0 + 2^1 + 2^2+\cdots +2^{k-1})\\
&= 2^k\cdot T(n^{1/2^k}) + n(2^k -1)
\end{align}$
Now, considering, $T(2)=1$ 
$n^{1/2^k}=2\implies k=\log_2(\log_2n)$
$\therefore T(n) \leq 2^{\log_2(\log_2n)} + n(\log_2n-1)=\mathcal{O}(n\cdot\log_2n)$
Now my questions are :  
1. Is there any tighter bound possible?
2. How to solve it using Master's Method?
If I assume, $n=2^m$, the recurrence becomes, 
$$T(2^m) = 2\cdot T(2^{m/2}) + 2^m$$
Let, $T(2^m) = S(m)$
$$S(m) = 2\cdot S(m/2) + 2^m$$ 
But can we apply Master's theorem here since $2^m$ is not polynomially larger than $m$?
 [/INST] We have
$$T(m^2)=2T(m)+m^2.$$
Then
$$T(4)=2T(2)+4,\\
T(16)=4T(2)+8+16,\\
T(256)=8T(2)+16+32+256,\\
T(65536)=16T(2)+32+64+512+65536,\\
\cdots\\
T(2^{2^k})=2^kT(2)+2^k2^2+2^{k-1}2^4+2^{k-2}2^8+\cdots2^{2^k},$$
which is
$$T(n)=\log_2n\ T(2)+\log_2n\,2^2+(\log_2n-1)2^4+(\log_2n-1)2^8+\cdots+n=O(n).$$
</s>