Just trying to solve this recursive equation. I tried to use an iteration method and I'm struggling to understand how to determine when the iteration is over (first iteration: $n^{0.5}$, second $n^{0.25}$, third $n^{0.125}$).
$$T(n) = T(\sqrt{n}) + 17$$
If the recurrence is actually $T(n) = T(\lfloor \sqrt n \rfloor) + 17$, then the solution is $T(n)=T(1)+17L(n)$, where $L(n) = k$ for $n \in [2^k,2^{k+1})$.
$L(n)$ is closely related to $\log_2^*(n)$, the iterated logarithm in base $2$.
A solution $T : (1,+\infty) \to \mathbb R$ is: $$ T(n) = 17 \log_{2}\log_2 n +\alpha\big(\log_{2}\log_2 n\big), \qquad n > 1 $$ where $\alpha$ is any real function with period $1$.
