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$?
 A: $$
T\left(2^{\log_2 n}\right)=2T\left(2^{\frac 12\log_2 n}\right)+n
$$
or
$$
\mathcal{T(\log_2 n)} = 2\mathcal{T}\left(\frac 12\log_2 n\right)+n
$$
or calling $z = \log_2 n$
$$
\mathcal{T}(z) = 2\mathcal{T}\left(\frac z2\right)+2^z
$$
or
$$
\mathcal{T}\left(2^{\log_2 z}\right) = 2 \mathcal{T}\left(2^{\log_2 \frac z2}\right)+2^z
$$
and after $u = \log_2 z$ we have
$$
\mathbb{T}(u) = 2 \mathbb{T}(u-1)+2^{2^u}
$$
Solving for $\mathbb{T}$ we obtain
$$
\mathbb{T}(u) = C_0 2^{u-1}+2^{u-1}\sum_{k=0}^{u-1}2^{2^{k+1}-k}
$$
and finally
$$ 
\mathbb{T}(u)\to\mathcal{T}(z)\to T(n)
$$
giving
$$
T(n) = \log_4 n\left(C_0+\sum_{k=0}^{\log_2(\log_2 n)-1}2^{2^{k+1}-k}\right)
$$
NOTE
making $u = \log_2(\log_2 n)-1$ we have
$$
2^{2^{u + 1} - u} \equiv \frac{n}{\log_4 n}
$$
A: 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).$$
