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?
-
$\begingroup$ Have another look at this $\endgroup$– Nicholas MancusoJan 14, 2014 at 17:15
-
$\begingroup$ @NicholasMancuso, thanks, that answers my question. What should we do now? Close this question, answer it? $\endgroup$– Alejandro PiadJan 14, 2014 at 17:39
2 Answers
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)$.
You can do without the Mastertheorem, by simply counting the number of nodes, since the overhead is constant. Let's assume $\forall n \leq 2: T(n) = 0$, then the height $k$ of the tree is bound by \begin{align*} n^{\frac{1}{2^k}} &\geq 2 \\ \Rightarrow n^{\frac{2^k}{2^k}} &\geq 2^{2^k} \\ \Rightarrow k &\leq \log_2\log_2 n \mbox{ .} \end{align*} So $T(n) \leq c[2^{k+1}-1] \leq 2c\log_2 n - c \in O(\log n)$.
-
$\begingroup$ There is a convincing argument that shows that $k=\log\log n$ in your case. Taking the square root of $n$ boils down to taking the 1st half of the binary representation of $n$. The length of $\text{bin}(n)$ is clearly $\log n$. And how often do you have to halve a value $x$ to get below 1? $\log x$ times. Putting this together shows that $k=\log\log n$. $\endgroup$– A.SchulzJan 16, 2014 at 11:05