Original Problem
$T(n) = 2T(\sqrt{n})+3$ and $T(2) = 3$
My Idea
- Compute the recursion tree height $h$
- Compute workload in each subproblem
- Compute how many subproblems are there in a layer
Question
I notice that $h$ satisfies $n^{\frac{1}{2}^h}=2$. But how to compute $h$?
The answer says $h\in \Theta(\log \log n)$, it still confuses me.
Would appreciate any help from you