I am trying to solve the recurrence $$T(n) = 5T(\sqrt{n}) + \log\log n$$ Assuming $n =2^m, m \in \mathbb{N}$, I got- $$S(m)= 5S\bigg(\frac{m}{2}\bigg) + \log m$$
I used the Akra-Bazzi method to solve it. To use the method I justified that $\log$ satisfies polynomial growth condition as for all $\Phi \geq 1$, we can choose constant $d = \Phi$, such that
$$\frac{\log n}{d} \leq \log(\Psi \cdot n) \leq d \log n $$
$\forall 1 \leq \Psi \leq \Phi$ and $ n \geq \hat{n} = 1$.
But I am not sure if this argument is correct as the bound I got is $>n^2$ which intuitively seems off since we are taking square root at each step and doing $\log \log n$ work.
Best Answer
$\log x$ definitely satisfies the polynomial growth condition since it is $O(x)$, but the Akra–Bazzi method does not need to be used to solve $S(m)$; the standard master theorem gives $T(2^m)=S(m)=\Theta(m^{\log_25})$ and thus $T(n)=\Theta((\log_2n)^{\log_25})$.