Contradicting asymptotic analysis in recurrence equation?

Question

I'm trying to solve the recurrence equation from CLRS ed 2. $$ T(n) = 2T(\sqrt{n}) + 1 $$ The question says the solution should be asymptotically tight, but at first I didn't read it and solved it with a substitution of variables and tried to find a big-O solution. $$ m = lg(n) \\ S(m) = T(2^m) \\ S(m) = 2S(m/2)+1 $$ After this, I guessed the solution to be O(lgn) and proved it; changing back the m's to be in the form of n I got T(n) to be O(lglgn).

However, this is not a tight bound and after changing my guess for S(m) from O(lgm) to Θ(m) it worked. The resulting analysis led me to T(n) being Θ(lgn).

Though this is the part that confuses me, how can a function be O(lglgn) yet Θ(lgn)? I can't seem to find my error.

Answer 1

Set $n=2^{2^m}$. The recurrence turns to

$$T(2^{2^m})=2T(2^{2^{m-1}})+1$$

or

$$S(m)=2S(m-1)+1.$$

This is an ordinary linear recurrence. By inspection it has the particular solution $S_p(m)=-1$, and the homogeneous part of the equation is solved by

$$S_h(m)=C\,2^m.$$

From this,

$$T(n)=S(m)=C\,2^m-1=C\,\log n-1.$$

---

Check:

$$C\,\log n-1=2(C\log\sqrt n-1)+1=\frac22C\,\log n-2+1.$$