# Solve the recurrence for $T(n) = T(\sqrt n) + 2$. Assume that T(n) is constant for $n\leqslant 2$.

Trying to work out the following question, but I'm stuck.. Can someone direct me please.

• Using a change of variables

$$\text{Let}\ m = \lg\ n \\ S (m) = T (2m)\\ T (2^{m}) = T (2^{m/2}) + 2 \\ S( m) = S (m/2) + 2$$

• Using Master Theorem

$$n\ log_b a = n\ log_2 1 = n^{0} = 1\text{ and }f (n) = 2$$

Since $1 < θ(2)$, case 1 applies and $S (m) = θ(\lg\ m^2), \quad\therefore T (n) \in \theta(\lg\lg{n^2})$

or

I was also thinking about the problem like this: \begin{align} T(n) &= T(\sqrt n ) + 2 = T(n^{1/2}) + 2 = T(n^{1/4}) + 4 = \cdots \\ &= T(n^{1/2^i}) + 2i = \cdots = T(n^{1/2^k}) + 2k\\ \end{align} $$n^{1/2^k} <=2 \\ \text{so } \log n = 1/(2^k) \\ k = \log (\frac{1}{\log n})$$ $$∴ T (n) ∈ θ(\lg \lg n)\ or\ T(n)\ \in θ(\log (\frac{1}{\log n}))$$

-
Or you go to the FAQ section and learn (it's easy, btw) how to properly type mathematics in this site with LaTeX, or your post will be very hard to decypher for many participants here and, perhaps, you won't get all the help you could otherwise. Read, as a sad example, your 2nd line: what on earth could " m = lg n S (m)..." possible mean?? –  DonAntonio Dec 1 '12 at 2:38
Please learn some $\LaTeX$ to format your posts. When I first came to this site I spent a few days learning it and now I'm rather sufficient at formatting. Plus, I love $\LaTeX$ now. Second, your "following question" is not embedded in your post. –  FrenzY DT. Dec 1 '12 at 2:40
just did, first time doing it. Thanks for the feedback –  user51348 Dec 1 '12 at 2:47
Thanks for and congratulations on a successful $\LaTeX$ update of your post. It makes it sooooo much easier to read. One small one-for functions like log, if you do \log you get $\log$ which is the proper font. I learned much of mine by right-clicking and selecting Show Math As -> TeX Ccommands –  Ross Millikan Dec 1 '12 at 2:50
thanks for the feedback guys :), really appreciate it. –  user51348 Dec 1 '12 at 2:51
Let $n = a^{2^m}$. Then $\sqrt{n} = a^{2^m/2} = a^{2^{m-1}}$. Letting $T(a^{2^m}) = g(m)$, we get that $$g(m) = g(m-1) + 2 = g(m-2) + 2 + 2 = g(m-3) + 2 + 2 +2 = g(0) + 2m$$ Note that $$\log_2(n) = 2^m \log_2(a) \implies \log_2(\log_2(n)) = m + \log_2(\log_2(a))$$ Hence, $$m = \log_2(\log_2(n)) - \log_2(\log_2(a))$$ This gives us that $$T(n) = 2 \log_2(\log_2(n)) - 2\log_2(\log_2(a)) + T(a)$$ Hence, $$T(n) = \mathcal{O}(\log_2(\log_2(n)))$$
Why not write something like "for $n\gt 2$ you have $T(n) = k + 2 \times \lceil \log_2 (\log_2 (n))\rceil$"? –  Henry Dec 1 '12 at 3:36