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
