Recurrence $T(n) = T(\sqrt{n}) + \Theta(\log_2\log_2n) $

Question

I want to solve the recurrence with iterative Method, but I don't know how to finish it. This is the last thing I solved, but how can I continue?

$$T(n) = T(n^{1/2^i}) + \displaystyle\sum_{i=1}^{\log_2\log_2n} n^{1/2^i}.\Theta(\log_2\log_2) $$ where $$k = \log_2\log_2n$$

Answer 1

From

$$ T(n) = T\left(\sqrt n\right)+\Theta\left(\log_2(\log_2 n)\right) $$

with $z = \log_2 n$ we have

$$ \mathbb T(z)=\mathbb T(z/2)+\Theta(\log_2 z) $$

and now with $u = \log_2 z$

$$ \mathcal T(u)=\mathcal T(u-1) + \Theta(u) $$

so

$$ \mathcal T(u) = C_0 + \sum_{k=0}^{u}\Theta(k) $$

now $\mathcal T(u)\rightarrow \mathbb T(z)\rightarrow T(n)$

hence

$$ T(n) = C_0 + \sum_{k=0}^{\log_2(\log_2 n)}\Theta(k) $$