Divide&Conquer, Arithmetic Problem

24 Views Asked by At

Original Problem

$T(n) = 2T(\sqrt{n})+3$ and $T(2) = 3$

My Idea

  1. Compute the recursion tree height $h$
  2. Compute workload in each subproblem
  3. 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