Give an asymptotic upper bound of this recurrence relation : $T(n) = 2\cdot T(n^{1/2}) + n$

Question

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$?

Answer 1

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

Answer 2

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