Solving the recurrency $T(n) = 2T(\sqrt{n}) + O(1)$

Problem Detail: 

I need to solve the following recurrency: $T(n) = 2T(\sqrt{n}) + O(1)$. It's for a simple undergrad problem that a student asked me, but I really couldn't solve it. Since it is for an undergrad question, it would be nice to solve it only with algebraic manipulation and reduction to a well known recurrence, or in the end use the master theorem or a recursion tree. Looking at this question, I tried to make $m=\log(n)$, but I got lost at squeezing the $\log$ inside the term $T(\sqrt{n})$. Is it like $T(\log(\sqrt{n}))$ or $T(\sqrt{\log(n)})$? Or is this the wrong approach?

Asked By : Alejandro Piad

Answered By : Michael

Since Master theorem is in terms of fractions of $n$ in the recurrence, and you have a fractional power of $n$ in the recurrence, try to convert between powers and multiplications. Taking $\log$ or $\exp$ of something usually helps with that.

Let $x=\log n$, $F(x)=T(\exp x)$. Then you have this recurrence:

$F(x)=T(\exp(\log n))=T(n)=2T(\sqrt n)+O(1)=2T(\exp (\frac{1}{2}\log(n)))+O(1)=2F(\frac{x}{2})+O(1)$

Then apply Master theorem to $F(x)$ and get $F(x)=O(x)$.

Therefore $T(n)=F(\log n)=O(\log n)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19717