2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Have another look at this $\endgroup$ Jan 14, 2014 at 17:15
  • $\begingroup$ @NicholasMancuso, thanks, that answers my question. What should we do now? Close this question, answer it? $\endgroup$ Jan 14, 2014 at 17:39

2 Answers 2

3
$\begingroup$

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)$.

$\endgroup$
0
1
$\begingroup$

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)$.

$\endgroup$
1
  • $\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.Schulz
    Jan 16, 2014 at 11:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.